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