# 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 –

Output:

Match

## Java

Output:

Match

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

Output:

Match

## Java

Output:

Match

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

(1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

### Leave a Reply

Subscribe
Notify of
Guest

excellent coding..

Guest
Top Coder

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

Guest

Thank you so much!

Guest
MessiCR7

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.

Guest
MessiCR7

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

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.