Wildcard Pattern Matching — Asked in Amazon, Microsoft, Walmart and Ola Interview

Problem Statement :

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:

True

Explanation of given Test Case :

Approach :

Iterative DP

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

  1. 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)

Code :

Thanks for Reading

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.

Upskilling students for tech placements!