5

Wildcard Pattern Matching

Difficulty: HARD
Avg. time to solve
50 min
Success Rate
30%

Problem Statement
Suggest Edit

Given a text and a wildcard pattern of size N and M respectively, implement a wildcard pattern matching algorithm that finds if wildcard pattern is matched with the text. The matching should cover the entire text not partial text.

The wildcard pattern can include the characters ‘?’ and ‘*’

 ‘?’ – matches any single character 
 ‘*’ – Matches any sequence of characters(sequence can be of length 0 or more)
Input Format:
The first line contains an Integer 't' which denotes the number of test cases/queries to be run. 
Then the test cases follow. 

The first line of input for each test case/query contains a string representing the wildcard pattern.
The second line of input for each test case/query contains a string representing the text.
Output Format:
For each test case, print ‘True’ if the text matches the pattern, print ‘False’ otherwise(without quotes).

Output for every test case will be printed in a separate line.
Note:
You do not need to print anything, it has already been taken care of. Just implement the function.
Constraints:
1 <= t <= 100
1 <= N <= 200
1 <= M <= 200
Text and pattern contains only lowercase letters and patterns may contain special characters ‘*’ and ‘?’

Time Limit: 1sec
Sample Input 1:
3
?ay
ray
ab*cd
abdefcd
ab?d
abcc
Sample Output 1:
True
True
False
Explanation of the Sample Input1:
Test Case 1:
The pattern is “?ay” and the text is ray.
‘?’ can match a character so it matches with a character ‘r’ of the text and rest of the text matches with the pattern so we print True.
 Test Case 2:
“ab” of text matches with “ab” of pattern and then ‘*’ of pattern matches with “def” of the text and “cd” of text matches with “cd” of the pattern. Whole text matches with the pattern so we print True.
Test Case 3:
“ab” of pattern matches with “ab” of text. ‘?’ of pattern matches with ‘c’ of the text but ‘d’ of the pattern do not match with ‘c’ of the text so we print False.
Want to solve this problem? Login now to get access to solve the problems