leetcode 10 正则表达式匹配

描述：

实现.和*号匹配，*表示前面字符0~无穷个，.表示任意一个字符。

要求全部，匹配，不是部分匹配。

解决：

思路类似最长公共子序列，

dp[i][j] = dp[i - 1][j - 1], 如果s[i] == p[j] || p[j] == '.'

dp[i][j - 2], 如果p[j] == '*' && s[i] != p[j - 1]

dp[i - 1][j] || dp[i][j - 1] || dp[i - 1][j - 1] || dp[i - 1][j - 2] || dp[i][j - 2], 如果p[j] == '*' && s[i] == p[j - 1]

稍稍解释下：

对于s和p，设各个最后一个字符为x, y，p的倒数第二字符为z，除此外前面字符设为S,P，则：

s = Sx

p = Pzy

如果x == y或y == '.'，则如果S和Pz匹配，则s和p匹配，因为最后两字字母是匹配的。这就缩减了问题规模。

而对于y == '*'的情况，需要考虑z：

如果x != z，则只有在s和P匹配的情况下，s和p才匹配。

如果x == z，设匹配符号为~吧，方便，则如果S~P，S~Pz，S~Pzy，Sx~P，Sx~Pz，都可得出s和p匹配。

代码压缩了空间，用一些额外变量保存会用到的变量。时间复杂度O(m*n)，空间复杂度O(n)。

bool cmatch(char s, char p) {
    return p == '*' || p == '.' || s == p;
}

bool isMatch(string s, string p) {
    int m = s.size();
    int n = p.size();
    bool* arr = new bool[n + 1]();
    arr[0] = 1;

    for (int i = 2; i <= n; ++i)
        if (p[i - 1] == '*' && arr[i - 2] == true) arr[i] = true;

    int j2 = arr[0];
    int j1 = arr[1];
    int sa = arr[2];

    for (int i = 1; i <= m; ++i) {
        for (int j = 0; j <= n; ++j)
            if (j == 0) {
                j2 = arr[0];
                arr[0] = false;
            }
            else if (j == 1) {
                j1 = arr[1];
                arr[1] = i == 1 && cmatch(s[0], p[0]);
            }
            else {
                sa = arr[j];
                if (p[j - 1] == '*')
                    arr[j] = cmatch(s[i - 1], p[j - 2]) && (arr[j] || arr[j - 1] || j1 || j2 || arr[j - 2])?true:arr[j - 2];
                else
                    arr[j] = cmatch(s[i - 1], p[j - 1])?j1:false;
                j2 = j1;
                j1 = sa;
            }
    }
    return arr[n];
}

leetcode 10 正则表达式匹配

推荐阅读