Wildcard Pattern Matching — Asked in Amazon, Microsoft, Walmart and Ola Interview
Problem Statement :
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)
Sample Input:
wildcard pattern = ?aytext = ray
Sample Output:
TrueExplanation of given Test Case :
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.
Approach :
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.
2. 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.
3. 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].
Time Complexity : O(N*M)
Space Complexity : O(N*M)
