刚好最近在学编译原理
有点想按照语法分析写。。不过用不着
因为知道正则表达式对一个串可能有多种匹配方法，所以要准备好回溯。
有最优子结构，一段s由一段p生成，于是dp。
常规思路是从前开始逐个字符匹配
这里想一下，倒着匹配考虑的情况少一些（其实是想正写发现太难了。。。囧）
dp[i][j]表示s[i:]可以由p[j:]生成（匹配。）于是就只需要考虑0-i-1，0-j-1的匹配
match是某个生成式的字符(x或.，而不是*)与某个串某个字符匹配
如s=abbb，p=ab*
bbb与b*匹配，每一个b都与b*的b匹match。
若匹配只有两种情况，单个.匹配和x*匹配。
具体处理
单个.匹配 dp[i][j] = first_match && dp[i+1][j+1]; //可能匹配到(match==true)，则推进一位
x*匹配 dp[i][j] = dp[i][j+2] ||match && dp[i+1][j]; //两种情况，可能使用p[j]，匹配不到，dp[i][j] = dp[i][j+2] ; 或可以匹配，则dp[i][j] =dp[i+1][j]，一个个字符推进(i+1)
复杂度分析看官方题解吧
注意初始化
没加false初始化
跑某个例子
dp[i][j] = match && dp[i+1][j+1];
class Solution { public: bool isMatch(string s, string p) { bool dp[s.length() + 1][p.length() + 1]; for(int i=0;i<=s.length();i++) for(int j=0;j<=p.length();j++) dp[i][j]=false; dp[s.length()][p.length()] = true; for (int i = s.length(); i >= 0; i--){ for (int j = p.length() - 1; j >= 0; j--){ bool match = (i < s.length() &&(p[j] == s[i] ||p[j] == ‘.‘)); if (j + 1 < p.length() && p[j+1] == ‘*‘){ //x*匹配 dp[i][j] = dp[i][j+2] || match && dp[i+1][j]; } else { //单个.匹配 dp[i][j] = match && dp[i+1][j+1]; } } } return dp[0][0]; } };
原文：https://www.cnblogs.com/lqerio/p/11746424.html