Check if a string matches with a given wildcard pattern

Given a string and a pattern containing wildcard characters, write an efficient algorithm to check if the input string matches with the wildcard pattern or not.


 

The ? wildcard character can match to any character in the input string and the * wildcard character can match to zero or more characters in the input string.

 

For example,


Input string = XYXZZXY, pattern = X***Y
Output: true

Input string = XYXZZXY, pattern = X***X
Output: false

Input string = XYXZZXY, pattern = X***X?
Output: true

Input string = XYXZZXY, pattern = *
Output: true

 

 
The idea is to recursively solve this problem by dividing the problem into sub-problems. For a given pattern[0..m] and str[0..n],

  1. If pattern[m] == *, if * matches with current character in input string we will move to next character in the string else we ignore the * character and move on to the next character in the pattern.
     
  2. If pattern[m] == ?, we ignore current characters of both string and pattern and check if pattern[0..m-1] matches str[0..n-1]
     
  3. If the current character in pattern is not a wildcard character, it should match with current character in the input string

 
Special care has to be taken to handle base conditions:

  1. If both input string and pattern reaches their end, we return true.
  2. If only pattern reaches its end, we return false.
  3. If only input string reaches its end, return true only when the remaining characters in the pattern consists of all *

 

Download   Run Code

 
The time complexity of above solution is exponential. We can use Dynamic Programming to bring down the time complexity to O(m*n) using O(m*n) extra space. The Dynamic Programming solution is demonstrated below in C++ using memoization –

 

Download   Run Code

 
Exercise: Implement Dynamic Programming solution using tabulation.

 
Thanks for reading.

Please use our online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
Notify of