44. Wildcard Matching (Hard)

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

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false

Solution 1: Greedy Alogrithm, Backtracking 15ms

这道题通配符匹配问题还是小有难度的，这道里用了贪婪算法Greedy Alogrithm来解，由于有特殊字符*和？，其中？能代替任何字符，*能代替任何字符串，那么我们需要定义几个额外的指针，其中scur和pcur分别指向当前遍历到的字符，再定义pstar指向p中最后一个*的位置，sstar指向此时对应的s的位置，具体算法如下：

• 定义scur, pcur, sstar, pstar

• 如果*scur存在

  • 如果*scur等于*pcur或者*pcur为 '?'，则scur和pcur都自增1

  • 如果*pcur为'*'，则pstar指向pcur位置，pcur自增1，且sstar指向scur

  • 如果pstar存在，则pcur指向pstar的下一个位置，scur指向sstar自增1后的位置

• 如果pcur为'*'，则pcur自增1

• 若*pcur存在，返回False，若不存在，返回True

bool isMatch(string s, string p) {
    char *scur = (char*)s.c_str(), *pcur = (char*)p.c_str(), *sstar = NULL, *pstar = NULL;
    while (*scur) {
        if (*scur == *pcur || *pcur == '?') {
            ++scur; ++pcur;
        } else if (*pcur == '*') {
            pstar = pcur++;
            sstar = scur;
        } else if (pstar) {
            pcur = pstar+1; // if not match, go to previous star position
            scur = ++sstar;
        } else {
            return false;
        }
    }

    while (*pcur == '*') ++pcur;
    return !*pcur;
}

version 2: 25ms

bool isMatch(string s, string p) {
    int m = s.size(), n = p.size();
    int si = 0, pi = 0, sstar = -1, pstar = -1;
    while (si < m) {
        if (pi < n && (p[pi] == '?' || s[si] == p[pi])) {
            ++pi; ++si;
        } else if (pi < n && p[pi] == '*') {
            pstar = pi++;
            sstar = si;
        } else if (pstar != -1) {
            pi = pstar+1; // if not match, go to previous star position
            si = ++sstar;
        } else {
            return false;
        }
    }
    while (pi < n) {
        if (p[pi++] != '*') return false;
    }
    return true;
}

Solution 2: DP 62ms

这道题也能用动态规划Dynamic Programming来解，写法跟之前那道题Regular Expression Matching很像，但是还是不一样。外卡匹配和正则匹配最大的区别就是在星号的使用规则上，对于正则匹配来说，星号不能单独存在，前面必须要有一个字符，而星号存在的意义就是表明前面这个字符的个数可以是任意个，包括0个，那么就是说即使前面这个字符并没有在s中出现过也无所谓，只要后面的能匹配上就可以了。而外卡匹配就不是这样的，外卡匹配中的星号跟前面的字符没有半毛钱关系，如果前面的字符没有匹配上，那么直接返回false了，根本不用管星号。而星号存在的作用是可以表示任意的字符串，当然只是当匹配字符串缺少一些字符的时候起作用，当匹配字符串包含目标字符串没有的字符时，将无法成功匹配。

Let's briefly summarize the idea of DP. We define the state P[i][j] to be whether s[0..i) matches p[0..j). The state equations are as follows:

1. P[i][j] = P[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '?'), if p[j - 1] != '*';
2. P[i][j] = P[i][j - 1] || P[i - 1][j], if p[j - 1] == '*'.

Equation 2). means that if p[j-1] is *, f(i,j) is true if either f(i,j-1) is true: s[0:i-1] matches p[0:j-2] and * is not used here; or f(i-1,j) is true: s[0:i-2] matches p[0:j-1] and * is used to match s[i-1].

bool isMatch(string s, string p) {
    int m = s.size(), n = p.size();
    vector<vector<bool>> dp(m+1,vector<bool>(n+1,false)); 
    dp[0][0] = true; // s = "", p = ""
    for (int i = 1; i <= n; ++i) { // s = ""
        if (p[i-1] != '*') break;
        dp[0][i] = true;
    }

    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (p[j-1] == '?' || s[i-1] == p[j-1]) dp[i][j] = dp[i-1][j-1];
            else if (p[j-1] == '*') dp[i][j] = dp[i][j-1] || dp[i-1][j];
            // else dp[i][j] = false;
        }
    }
    return dp[m][n];
}