Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for ‘?’ and ‘*’.
'?' Matches any single character. '*' Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string .
Example 1: Input: s = "aa" p = "a" Output: false Explanation: "a" does not match the entire string "aa".
Example 2: Input: s = "aa" p = "*" Output: true Explanation: '*' matches any sequence.
Example 3: Input: s = "cb" p = "?a" Output: false Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.
Example 4: Input: s = "adceb" p = "*a*b" Output: true Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".
Example 5: Input: s = "acdcb" p = "a*c?b" Output: false
Before going through the solution, I recommend you to read a similar problem of “regular expression matching”.
This problem can be solved using Dynamic Programming. We shall be taking a Boolean array and update it according to the below 2 formulas. At the end of the array, we shall get the result.
Formula:
1. boolean_array[i][j] = boolean_array[i-1][j-1] if the value at boolean_array[i][j] is a character or a “?”. 2. boolean_array[i][j] = boolean_array[i][j-1] || boolean_array[i-1][j] if the value at at boolean_array[i][j] is “*”.
To understand the problem better we shall take an example and solve step by step.
In our example,
String = “xaylmz” Pattern = “x?y*z”
The initial Boolean array will be as shown below:
boolean_array [0][0] = True. Because consider an empty string and an empty pattern, they both will match. Hence true.
boolean_array [0][1] = False. Because the pattern is “x” and the string is “null”. They will not match. Hence false.
With the same analysis, the whole column will become false as shown below.
Now, boolean_array [1][0] = False. Because the pattern is “null” and the string is “x”. They will not match. Hence the whole row will be false.
Now, boolean_array [1][1] = True. Because the pattern is “x” and string is also “x”. This matches our first condition. Value of boolean_array [1][1] = boolean_array [0][0], which is true.
Now, boolean_array [1][2] = False. Because the pattern is “x?” and the string is “x”. This matches our first condition. Value of boolean_array [1][2] = boolean_array [0][1], which is False.
Now, boolean_array [1][3] = False. Because the pattern is “y” and string is “x”. Hence is false.
Now, boolean_array [1][4] = False. Since the pattern is “*”, we look at the value at left and top, [represented in purple], since both are false, the result is false.
Now, boolean_array [1][5] = False. Since the pattern is “z” and string is “x”, false.
Once we solve all the index, finally we get the value “true” as shown in green color in below image.
Solution in C++
#include<iostream> #include<vector> using namespace std; bool isMatch(string str, string pattern) { bool bool_array [str.size()+1] [pattern.size()+1]; //initialize boolean array to false. for (int i = 0; i <= str.size(); ++i) { for (int j = 0; j <= pattern.size(); ++j) { bool_array[i][j] = 0; } } // base case bool_array[0][0] = true; for (int i = 1; i <= str.size(); i++) { for (int j = 1; j <= pattern.size(); j++) { if (str[i-1] == pattern[j-1] || pattern[j-1] == '?') bool_array[i][j] = bool_array[i-1][j-1]; else if (pattern[j-1] == '*') bool_array[i][j] = bool_array[i][j-1] || bool_array[i-1][j]; } } return bool_array[str.size()][pattern.size()]; } int main() { string str = "xaylmz"; string pattern = "x?y*z"; bool result = isMatch(str, pattern); if(result) cout<<" The pattern and string matches"<<endl; else cout<<" The pattern and string does not match"<<endl; return 0; }
Output:
The pattern and string matches