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

DP的方法要先建立一個size為(m + 1) * (n + 1)的2D dp table，dp[i][j]代表s[0...i - 1]和p[0...j-1]是否match。 dp[0][j] = dp[0][j - 1] if j > 1 and p[j - 1] == '*' 1. dp[i][j] = dp[i - 1][j - 1] if s[i - 1] == p[j - 1] || p[j - 1] == '?' 2. dp[i][j] = dp[i - 1][j] || dp[i][j - 1] if p[j - 1] == '*' dp[i - 1][j]的情形是s[0...i - 2]和p[0...j - 1]match然後p[j - 1]這個'*'要match更多的characters。 dp[i][j - 1]的情形是s[0...i - 1]和p[0...j - 2]match然後p[j - 1]這個'*'要match empty sequence。

// Dynamic programming
bool isMatch(string s, string p) { // time: O(m * n); space: O(m * n)
    int m = s.length(), n = p.length();
    vector<vector<bool> > dp(m + 1, vector<bool>(n + 1, false));
    dp[0][0] = true;
    for (int j = 1; j <= n; ++j) {
        dp[0][j] = dp[0][j - 1] && p[j - 1] == '*';
    }
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (p[j - 1] == '*') {
                dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                // dp[i][j - 1]: * represents empty sequence since s[0...i) matches p[0...j-1)
                // dp[i - 1][j]: * represents one more characters since s[0...i-1) matches p[0...j)
            } else {
                dp[i][j] = dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '?');
            }
        }
    }
    return dp.back().back();
}

// Space Optimized Dynamic Programming
bool isMatch(string s, string p) { // time: O(m * n); space: O(n)
    int m = s.length(), n = p.length();
    vector<bool> dp(n + 1, false);
    dp[0] = true;
    for (int j = 1; j <= n; ++j) {
        dp[j] = dp[j - 1] && p[j - 1] == '*';
    }
    for (int i = 1; i <= m; ++i) {
        int upper_left = dp[0];
        dp[0] = false;
        for (int j = 1; j <= n; ++j) {
            int upper = dp[j];
            if (p[j - 1] == '*')
                dp[j] = dp[j - 1] || upper;
            else
                dp[j] = upper_left && (s[i - 1] == p[j - 1] || p[j - 1] == '?');
            upper_left = upper;
        }
    }
    return dp.back();
}

// Greedy
bool isMatch(string s, string p) { // time: O(m or n); space: O(1)
    int m = s.length(), n = p.length();
    int i = 0, j = 0, match = -1, asterisk = -1;
    while (i < m) {
        if (j < n && (p[j] == s[i] || p[j] == '?')) {
            ++i;
            ++j;
        } else if (j < n && p[j] == '*') { // find *, move j forward
            match = i;
            asterisk = j++;
        } else if (asterisk >= 0) { // last pattern is *, move i forward
            i = ++match;
            j = asterisk + 1;
        } else return false;
    }
    while (j < n && p[j] == '*') ++j;
    return j == n;
}