字符串处理

没想到是动态规划题，感觉特别难 LCR 137. 模糊搜索验证 – 力扣（LeetCode）

法1：DP

用f[i][j]表示s的前i个字符与p的前j个字符是否能匹配。
考虑情况：

1. p的第j个字符是小写字符：
   f[i][j] = f[i-1][j-1] （if s[i] = p[j]）
   f[i][j] = false （if s[i] ≠ p[j]）
   
2. p的第j个字符是*：如果 p 的第 j 个字符是 *，那么就表示我们可以对 p 的第 j−1 个字符匹配任意自然数次。在匹配 0 次的情况下，我们有：f[i][j] = f[i-1][j-2]
   

实际上，本质上只会有两种情况：

• 匹配 s 末尾的一个字符，将该字符扔掉，而该组合还可以继续进行匹配；
• 不匹配字符，将该组合扔掉，不再进行匹配

代码：

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size();
        int n = p.size();

        auto matches = [&](int i, int j) {
            if (i == 0) {
                return false;
            }
            if (p[j - 1] == '.') {
                return true;
            }
            return s[i - 1] == p[j - 1];
        };

        vector<vector<int>> f(m + 1, vector<int>(n + 1));
        f[0][0] = true;
        for (int i = 0; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p[j - 1] == '*') {
                    f[i][j] |= f[i][j - 2];
                    if (matches(i, j - 1)) {
                        f[i][j] |= f[i - 1][j];
                    }
                }
                else {
                    if (matches(i, j)) {
                        f[i][j] |= f[i - 1][j - 1];
                    }
                }
            }
        }
        return f[m][n];
    }
};

法2：递归

贴个leetcode的递归版本代码，更容易理解

class Solution {
public:
    bool isMatch(string s, string p) 
    {
        if (p.empty())  return s.empty();
        bool first_match = !s.empty() && (s[0] == p[0] || p[0] == '.');
        // *前字符重复>=1次 || *前字符重复0次（不出现）
        if (p.size() >= 2 && p[1] == '*')  
            return (first_match && isMatch(s.substr(1), p)) || isMatch(s, p.substr(2));
        // 不是*，剪去已经匹配成功的头部，继续比较
        else
            return first_match && isMatch(s.substr(1), p.substr(1));    
    }
};