PROBLEM

剑指 Offer 19. 正则表达式匹配

难度 困难

MY ANSWER

写一晚上没写出来。

BETTER SOLUTION

动态规划

用dp[i][j]表示s的前i个字符和p的前j个字符是否能匹配，由于 dp[0][0] 代表的是空字符的状态， 因此 dp[i][j] 对应的添加字符是 s[i - 1] 和 p[j - 1]。时间复杂度O(mn)，空间复杂度O(mn)。

  • 当 p[j - 1] = '*' 时， dp[i][j] 在当以下任一情况为 true 时等于 true ：
    • dp[i][j - 2]： 即将字符组合 p[j - 2] * 看作出现 0 次时，能否匹配；
    • dp[i - 1][j] 且 s[i - 1] = p[j - 2]: 即让字符 p[j - 2] 多出现 1 次时，能否匹配；
    • dp[i - 1][j] 且 p[j - 2] = '.': 即让字符 '.' 多出现 1 次时，能否匹配；
  • 当 p[j - 1] != '*' 时， dp[i][j] 在当以下任一情况为 true时等于 true：
    • dp[i - 1][j - 1] 且 s[i - 1] = p[j - 1]： 即让字符 p[j - 1] 多出现一次时，能否匹配；
    • dp[i - 1][j - 1] 且 p[j - 1] = '.'： 即将字符 . 看作字符 s[i - 1] 时，能否匹配；
  • 初始化： 需要先初始化 dp 矩阵首行，以避免状态转移时索引越界。
    • dp[0][0] = true
    • **dp[0][j] = dp[0][j - 2] 且 p[j - 1] = '*'**：首行 s 为空字符串，因此当 p 的偶数位为 * 时才能够匹配（即让 p 的奇数位出现 0 次，保持 p 是空字符串）。因此，循环遍历字符串 p ，步长为 2（即只看偶数位）。
class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size() + 1, n = p.size() + 1;
        vector<vector<bool>> dp(m, vector<bool>(n, false));
        dp[0][0] = true;
        for(int j = 2; j < n; j += 2)
            dp[0][j] = dp[0][j - 2] && p[j - 1] == '*';
        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                dp[i][j] = p[j - 1] == '*' ?
                    dp[i][j - 2] || dp[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'):
                    dp[i - 1][j - 1] && (p[j - 1] == '.' || s[i - 1] == p[j - 1]);
            }
        }
        return dp[m - 1][n - 1];
    }
};

SUMMARY

动态规划最主要的是分析得出状态转移方程。