题目描述

请实现一个函数用来匹配包含’. ‘和’‘的正则表达式。模式中的字符’.‘表示任意一个字符，而’'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但与"aa.a"和"ab*a"均不匹配。

https://leetcode.cn/problems/zheng-ze-biao-da-shi-pi-pei-lcof/

题解

状态转移方程看力扣官方题解

对于 ‘*’ 匹配状态转移，自己动手写写画画就理解了，编码时还有一些细节问题要注意。

动态规划

// 二维动态规划
// f[i][j]: s 的长度为 i, p 的长度为 j 时，s 和 p 是否匹配
// 边界值处理：j 为 0 时不匹配，即 f[0][j] = false，特殊的 f[0][0] = true
// 当 i 为 0 时，可能匹配，如：s = "", p = "a*", "*"可以匹配 0 个
// 状态转移方程：
// p[j - 1] != '*' 时，if match(s[i - 1], p[j - 1]) f[i][j] = f[i - 1][j - 1]，else f[i][j] = false
// p[j - 1] == '*' 时，if match(s[i - 1], p[j - 2]) f[i][j] = f[i][j - 2] | f[i - 1][j]
//                     else f[i][j] = f[i][j - 2]
// 关于 p[j - 1] == '*' 时，如果 s[i - 1] 和 p[j - 2] 匹配，那我们可以选择匹配或不匹配
//                          如果不匹配，那只能选不匹配
class Solution {
public:
    bool isMatch(string s, string p) {
        int slen = s.size(), plen = p.size();
        auto match = [&](int i, int j) -> bool {    // 这里的 i, j 也是长度
            // '*' 在外面处理，这里只返回单个字符的的匹配结果
            // 如果 s 的长度为 0，那不匹配（j 不会小于 0，特殊情况已经处理过了，这里不考虑
            return i == 0 ? false : s[i - 1] == p[j - 1] || p[j - 1] == '.';
        };
        vector<vector<bool>> f(slen + 1, vector<bool>(plen + 1, false));
        f[0][0] = true;
        // i, j 是长度，别忘了是 <= 而不是 < ...
        for (int i = 0; i <= slen; i++) {        // i = 0 的情况还是要考虑的
            for (int j = 1; j <= plen; j++) {    // j = 0 的情况一定不匹配（除了f[0][0]）
                if (p[j - 1] != '*') {
                    if (match(i, j)) f[i][j] = f[i - 1][j - 1];
                } else {
                    if (match(i, j - 1)) f[i][j] = f[i][j - 2] | f[i - 1][j];   // 不匹配或匹配
                    else f[i][j] = f[i][j - 2];     // 不匹配
                }
            }
        }
        return f[slen][plen];
    }
};