模式匹配

通配符匹配

https://leetcode.com/problems/wildcard-matching/

支持：?匹配单个字母和 *匹配 0 或多个字母

bool isMatch(string s, string p) {
    // 设dp[i][j]表示s[i..]和p[j..]匹配，则
    //   当s[i]==p[j] || p[j]=='?'时，dp[i][j] = dp[i+1][j+1]
    //   当p[j]=='*'时，dp[i][j] = dp[i][j+1] /*匹配0个*/ || dp[i+1][j] /*匹配1个或多个*/
    //   否则，dp[i][j]=false
    // 初始化，s匹配完、p也匹配完，dp[M][N]=true；或者，s匹配完、p剩下的全是*，dp[M][,..]=true
    const int M = s.size(), N = p.size();
    vector<vector<bool>> dp(M + 1, vector<bool>(N + 1, false));
    dp[M][N] = true;
    for (int j = N - 1; j >= 0 && p[j] == '*'; j--) {
        dp[M][j] = true;
    }

    for (int i = M - 1; i >= 0; i--) {
        for (int j = N - 1; j >= 0; j--) {
            if (s[i] == p[j] || p[j] == '?') dp[i][j] = dp[i+1][j+1];
            else if (p[j] == '*') dp[i][j] = dp[i][j+1] || dp[i+1][j];
            else dp[i][j] = false;
        }
    }
    return dp[0][0];
}

正则表达式匹配

https://leetcode.com/problems/regular-expression-matching/

支持：. 匹配任意字母和 x*匹配 0 或多个 x

bool isMatch(string s, string p) {
    // 设dp[i][j]表示s[i..]和p[j..]匹配，0<=i<=M，0<=j<=N，则
    // matchOne = i<M && (s[i]==p[j] || p[j]=='.')
    // 当p[j+1]=='*'
    //     dp[i][j] = dp[i][j+2] // 匹配0次
    //     dp[i][j] ||= matchOne && dp[i+1][j] // 递归匹配多次
    // 当p[j+1]!='*'
    //     dp[i][j] = matchOne && dp[i+1][j+1]
    // 初始dp[M][N]=true, dp[<M][N]=false

    const int M = s.size(), N = p.size();
    vector<vector<bool>> dp(M + 1, vector<bool>(N + 1, false));
    dp[M][N] = true; // dp[][N]的其他情况为false

    for (int i = M; i >= 0; i--) {
        for (int j = N - 1; j >= 0; j--) {
            bool matchOne = i < M && (s[i] == p[j] || p[j] == '.');
            if (j + 1 < N && p[j+1] == '*') { // look ahead
                dp[i][j] = dp[i][j+2] || (matchOne && dp[i+1][j]);
            } else {
                dp[i][j] = matchOne && dp[i+1][j+1];
            }
        }
    }
    return dp[0][0];
}

// 递归
bool isMatch(string s, string p) {
    return match(s, 0, p, 0);
}

bool match(const string &s, int si, string &p, int pi) {
    const int M = s.size(), N = p.size();
    if (pi == N) return si == M;
    bool matchOne = si < M && (s[si] == p[pi] || p[pi] == '.');
    if (pi + 1 < N && p[pi+1] == '*') {
        return match(s, si, p, pi + 2) || (matchOne && match(s, si + 1, p, pi));
    } else {
        return matchOne && match(s, si + 1, p, pi + 1);
    }
}

https://leetcode.com/problems/word-pattern/
https://leetcode.com/problems/find-and-replace-pattern/

bool wordPattern(string pattern, string str) {
    // 把一一对应的pattern中字母和str中单词同时映射到[1..N]
    unordered_map<char, int> p2i;
    unordered_map<string, int> w2i;
    string w;
    istringstream iss(str);
    int i = 0, N = pattern.size();
    while (iss >> w) {
        if (i == N) return false; // str中单词更多
        char p = pattern[i];
        if (p2i[p] != w2i[w]) return false;
        p2i[p] = w2i[w] = ++i;
    }
    return i == N;
}