Wildcard Matching

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 (not partial).

Note:

s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like ? or *.

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”.

Given an input string (s) and a pattern (p), implement regular expression matching with support for ‘.’ and ‘*’.

The above 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”

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 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 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++

/*
* File     : wild_card_pattern_matching.cpp
* Author   : ajay.thousand@gmail.com
* Copyright: @ prodevelopertutorial.com
*/
#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