leetcode：10. 正则表达式匹配（动态规划）

链接：https://leetcode-cn.com/problems/regular-expression-matching/
创建二维数组$dp$，$dp[i][j]$代表字符串s的前$i$个字符和字符串p的前$j$个字符能否匹配。考虑$dp[i][j]$的状态转移方程：

1. 当$p[j]$为字母时，它必须等于$s[i]$，且$dp[i-1][j-1]$为$true$时$dp[i][j]$为true
2. 当$p[j]$为$.$时，$dp[i-1][j-1]$为$true$时$dp[i][j]$为true
3. 当$p[j]$为$\ast$时，我们需要枚举这个$\ast$匹配的元素个数（$0-i$）

边界条件：

1. $s,p$均为空串时匹配
2. $s$为空串,$p$不为空串，只有$p$是字符与星号交替出现是匹配
3. $p$为空串$s$不为空串是不匹配。

C++代码：

class Solution {
public:
    bool isMatch(string s, string p) {
        int s_size = s.size();
        int p_size = p.size();
        vector<vector<bool>> dp(s_size+1,vector<bool>(p_size+1,false));
        dp[0][0] = true;
        for(int i = 2;i<p_size+1;i+=2)
        {
            if(p[i-1]=='*')
                dp[0][i] = true;
            else 
                break;
        }
        for(int i = 1;i<=s_size;i++)
        {
            for(int j = 1;j<=p_size;j++)
            {
                if(p[j-1]=='.')
                    dp[i][j] = dp[i-1][j-1];
                else if(p[j-1]=='*')
                {
                    if(j==1)
                        dp[i][j] = false;
                    else if(p[j-2]=='.')
                        for(int k = 0;k<=i;k++)
                            dp[i][j]  = dp[i][j]||dp[k][j-2];
                    else
                    {
                        int k = i-1;
                        while(k>=0&&s[k]==p[j-2])
                        {
                            dp[i][j] = dp[i][j]||dp[k][j-2];
                            k--;
                        }
                        dp[i][j] = dp[i][j]||dp[i][j-2];
                    }
                }
                else 
                    dp[i][j] = (s[i-1]==p[j-1])&&dp[i-1][j-1];
            }
        }
        return dp[s_size][p_size];
    }
};