Wildcard Pattern Matching
Given a text and a wildcard pattern of size N and M respectively, implement a wildcard pattern matching algorithm that finds if the 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

Question

Wildcard Pattern Matching

Given a text and a wildcard pattern of size N and M respectively, implement a wildcard pattern matching algorithm that finds if the 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

Where 'N' denotes the length of 'TEXT' and 'M' denotes the length of 'PATTERN'.

'TEXT' and 'PATTERN' contain only lowercase letters and patterns may contain special characters ‘*’ and ‘?’

Time Limit: 1sec

Accepted Answer

Brute Force

We will try to explore all the possibilities using the recursion.

Let’s say we have a recursive function ‘REC’ who has two arguments IDX and IDY where IDX represents the index in the text string and IDY represents the index in pattern string and its return type is boolean. Initially, we will call the rec with IDX = N and IDY = M where N is the size of the text string and M is the size of the pattern string.

If IDX == 0 && IDY == 0
- It means we have reached end of both text and pattern so return true
If IDY == 0
- It means we have reached the end of the pattern but there are some characters left in the text so we should return false.
If IDX == 0
- It means we have reached the end of the text but there are some characters left in the pattern so we should check if all the left characters are ‘*’ then return true otherwise return false.

We have taken care of the base cases now we need recursive relation to explore the cases. Create a variable RET = 0 to store the answer.

If TEXT[IDX-1] == PATTERN[IDY-1] || PATTERN[IDY-1] == ‘?’
- RET |= REC(IDX-1,IDY-1)
- It means if the character at IDX-1 of TEXT and IDY-1 of pattern matches we can reduce the length of both by 1.
If PATTERN[IDY-1] == ‘*’
- RET |= REC(IDX-1,IDy) // Matches current character of text and ‘*’ can match more characters of the text.
- RET |= REC(IDX,IDY-1) // Stopped matching the characters with ‘*’
Return the RET which has our required answer.

Space Complexity: O(1)Explanation:

O(N*M), where N is the size of the text and M is the size of the pattern string.

Since here at worst case, our recursion will need O(N*M) stack space for the recursive calls that we are making based on the character choices ‘?’ and ‘*’ therefore we are populating two more calls from every single call in the search space due to which the space complexity here is of the order of O(N*M).

Time Complexity: OtherExplanation:

O(2^(N*M), where N is the size of the text and M is the size of the pattern string

Here, in each recursive call to the function we are making two more separate calls based on the character choices ‘?’ and ‘*’ therefore we are populating two more calls from every single call in the search space due to which the complexity here grows by the order of O(2^(N*M)).

Accepted Answer

Memoization

Let’s say we have a recursive function ‘REC’ who has two arguments IDX and IDY where IDX represents the index in the text string and IDY represents the index in pattern string and its return type is boolean. Initially, we will call the rec with IDX = n and IDY = m where n is the size of the text string and m is the size of the pattern string. We will have an N*M size matrix ‘DP’ to do the memoization.

If IDX == 0 && IDY == 0
- It means we have reached the end of both text and pattern so return true
If IDY == 0
- It means we have reached the end of the pattern but there are some characters left in the text so we should return false.
If IDX == 0
- It means we have reached the end of the text but there are some characters left in the pattern so we should check if all the left characters are ‘*’ then return true otherwise return false.
Now we will check if this state of IDX and IDY has already been calculated or not
- if( DP[IDX][IDY]!=-1) return DP[IDX][IDY]

We have taken care of the base cases now we need recursive relation to explore the cases. Create a variable RET = 0 to store the answer.

If TEXT[IDX-1] == PATTERN[IDY-1] || PATTERN[IDY-1] == ‘?’
- RET |= REC(IDX-1,IDY-1)
- It means if the character at IDX-1 of TEXT and IDY-1 of pattern matches we can reduce the length of both by 1.
If PATTERN[IDY-1] == ‘*’
- RET |= REC(IDX-1,IDY) // Matches current character of text and ‘*’ can match more
- RET |= REC(IDX,IDY-1) // Stopped matching the characters with ‘*’.

Store the value of ret at DP[IDX][IDY] that is memoized this state

DP[IDX][IDY] = RET

And then return the RET.

Space Complexity: O(m*n) - For 2d arraysExplanation:

O(N*M), where N is the size of the text and M is the size of the pattern string

We are creating an N*M dimensional matrix to do the memoization.

Time Complexity: O(m*n) - For 2d arraysExplanation:

O(N*M), where N is the size of the text and M is the size of the pattern string

Because we are memoizing the calculations and in the worst case, it will take O(M*N) time complexity.

Accepted Answer

Iterative DP

Let’s define DP[i][j] as DP[i][j is true if first i characters in given text matches the first j characters of pattern.

Create a N*M dimensional array DP where N is the size of the text and M is the size of the pattern string.

Let’s take care of base cases first.

DP[0][0] = 1 // Because if text and pattern are empty strings they matches.
DP[i][0] = 0 // Because if the size of the pattern is 0 then any length of the text will not match with the pattern except 0 length text.
DP[0][j] = DP[0][j-1] when the j’th character is ‘*’.

Now run two loop first from i = 1 to i = N and second loop from j = 1 to j = M and we will use same recursive relation here i.e

If TEXT[i-1] == PATTERN[j-1] or PATTERN[j-1]==’?’
- DP[i][j]=DP[i-1][j-1]
- That is if the current characters matches then our answer will be whatever the answer was for one length smaller text and 1 length smaller pattern.
If PATTERN[j-1]=’*’
- DP[i][j] = DP[i - 1][j] or DP[i][j - 1] or DP[i - 1][j - 1];
- ‘*’ can match 0 or more characters so we will have three option here.
Otherwise
- DP[i][j]=0
- That is the current characters do not match.

Now our answer is at DP[N][M] so return the value at DP[N][M].

Space Complexity: O(m*n) - For 2d arraysExplanation:

O(N*M), where N is the size of the text and M is the size of the pattern string

We are creating an N*M dimensional matrix.

Time Complexity: O(m*n) - For 2d arraysExplanation:

O(N*M), where N is the size of the text and M is the size of the pattern string

Because we are running two nested loops of size N*M.

Given a text and a wildcard pattern of size N and M respectively, implement a wildcard pattern matching algorithm that finds if the 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 ‘*’

Input Format:

Output Format:

Note:

Constraints:

Top Goldman Sachs Analyst interview questions & answers

Popular interview questions of Analyst

Top HR questions asked in Goldman Sachs Analyst