10.正则表达式匹配

思路

动态规划

状态转移：

1. 第一个就不解释了

2. 当p[j] == '*'时，*可以表示任意个p[j - 1]字符，

   如果表示0个p[j - 1]，那就是F(i, j) = F(i, j - 2)，即s[1~i]和p[1~j-2]匹配

   如果表示1个p[j - 1]，那就是F(i, j) = F(i - 1, j - 2) && s[i] == [j - 1]
   即s[1~i - 1]和p[1~j-2]匹配，且s[i] == p[j - 1]

   其他个数同理

对第二个状态转移进行优化

因为\(F(i - 1, j) = F(i-1,j-2) || \{F(i-2, j-2) \& S[i-1]==p[j-1]\} || \{F(i-3, j-2) \& S[i-1] \& S[i-2]\} ...\)

显然跟第二个转移方程只相差后半段中的s[i]==p[j-1] ，因此原方程可转换成

\(F(i, j) = f(i, j-2) || {f(i-1, j) \& s[i] == p[j - 1] }\)

特殊情况

将 '字符 + *'当做一个整体来处理，因此如果某个字符的下一个字符是*，就跳过当前字符。

如果字符处理一次,*再处理一次,会发生重复处理的情况,因此可以跳过字符

代码

class Solution {
public:
    bool isMatch(string s, string p) {
      	//方便边界处理
        s = ' ' + s, p = ' ' + p;
        vector<vector<bool>> dp(n + 1, vector<bool>(m + 1));
        dp[0][0] = true;
        
        for(int i = 0; i < s.size(); i++)
            for(int j = 1; j < p.size(); j++)
            {
                if(j + 1 < p.size() && p[j + 1] == '*') continue;
                if(i && p[j] != '*') dp[i][j] = dp[i - 1][j - 1] && (s[i] == p[j] || p[j] == '.');
                else if(p[j] == '*') dp[i][j] = dp[i][j - 2] || i && dp[i - 1][j] && (s[i] == p[j - 1] || p[j - 1] == '.');
            }
        return dp[s.size() - 1][p.size() - 1];
    }
};