44 Wildcard Matching

1. Dynamic Programing

bool isMatch(string s, string p)
{
    vector<vector<bool>> dp(s.size() + 1, vector<bool>(p.size() + 1, false));
    dp[0][0] = true;
    for (int i = 0; i < p.size(); i++)
    {
        if (p[i] == '*')
        {
            dp[0][i + 1] = dp[0][i];
        }
    }
    for (int i = 0; i < s.size(); i++)
    {
        for (int j = 0; j < p.size(); j++)
        {
            if (s[i] == p[j] || p[j] == '?')
            {
                dp[i + 1][j + 1] = dp[i][j];
            }
            else if (p[j] == '*')
            {
                dp[i + 1][j + 1] = dp[i][j] || dp[i][j + 1] || dp[i + 1][j];
            }
        }
    }
    return dp.back().back();
}

Space	Time
$O(S \times P)$	$O(S \times P)$

2. Linear time solution

bool isMatch(string s, string p)
{
    int i = 0, j = 0, jj = -1, ii = 0;
    while (i < s.size())
    {
        if (j < p.size() && s[i] == p[j] || p[j] == '?')
        {
            j++;
            i++;
        }
        else if (j < p.size() && p[j] == '*')
        {
            jj = j++;
            ii = i;
        }
        else if (jj != -1)
        {
            j = jj + 1;
            i = ++ii;
        }
        else
        {
            return false;
        }
    }
    while (j < p.size() && p[j] == '*')
    {
        j++;
    }
    return j == p.size();
}

Space	Time
$O(1)$	$O(S + P)$