Wildcard Pattern Matching


Wildcard Pattern Matching: Given a string and a pattern containing wildcard characters i.e. ‘*’ and ‘?’, where ‘?’ can match to any single character in input string and ‘*’ can match to any number of characters including zero characters, design an efficient algorithm to find if the pattern matches with the complete input string or not.

 

For example,


Input: string = “xyxzzxy”, pattern = “x***y”
Output: Match

Input: string = “xyxzzxy”, pattern = “x***x”
Output: No Match

Input: string = “xyxzzxy”, pattern = “x***x?”
Output: Match

Input: string = “xyxzzxy”, pattern = “*”
Output: Match

 

 
The idea is to use Dynamic Programming to solve this problem. If we carefully analyze the problem, we can see that it can easily be further divided into sub-problems. Let’s take top-bottom approach to solve this problem.

For a given pattern[0..m] and str[0..n],

  • If pattern[m] == ‘*’, if ‘*’ matches with current character in input string we will move to next character in the string else we ignore ‘*’ and move to next character in the pattern.
     
  • If pattern[m] == ‘?’, we ignore current characters of both string and pattern and check if pattern[0..m-1] matches str[0..n-1]
     
  • 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:

  • If both input string and pattern reaches their end, we return true.
     
  • If only pattern reaches its end, we return false.
     
  • If only input string reaches its end, return true only if remaining characters in the pattern are all ‘*’

 
Below is top-down DP solution in C and Java using memoization –

C

Download   Run Code

Output:

Match

Java

Download   Run Code

Output:

Match

 
Below is iterative C++ and Java implementation of the above code:

C++

Download   Run Code

Output:

Match

Java

Download   Run Code

Output:

Match

 
The time complexity of above solution is O(n2) and auxiliary space used by the program is O(n2).

 
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  
newest oldest most voted
Notify of
Somil
Guest

excellent coding..

Top Coder
Guest

Iterative version – http://cpp.sh/8hhiy

Ildar
Guest

Thank you so much!

MessiCR7
Guest

For the recursive solution, when the pattern is ‘*’, shouldn’t there be an additional case of checking for isMatching(m-1,n-1)
so if pattern[m] is *, then we either move on to the next element in both strings, or in just one of the two strings, so in total three possibilities, but your code has taken into consideration only two possibilities, i.e. either move to next element in str, or in pattern. It could move to next element in both strings too.

MessiCR7
Guest

Ah, got it. The third case is automatically accounted for in the two cases already considered. Nice.

foobar
Guest

In case someone has a similar doubt.

(2) case Ignore * and move to the next character in the pattern because * implies 0 or matches.