全文参考labuladong
dp[i][j] 表示 s 的前 i 个是否能被 p 的前 j 个匹配
dp[0][0]=true # s与j是" "空字符，当然可以匹配
怎么想转移方程？首先想的时候从已经求出了 dp[i-1][j-1]入手，再加上已知 s的第i个字母s[i-1]、p的第j个字母p[j-1]，要想的问题就是怎么去求 dp[i][j]
分情况讨论：
考虑最简单的 p[j-1] == s[i-1] : dp[i][j] = dp[i-1][j-1]从 p[j] 可能的情况来考虑，让 p[j]=各种能等于的东西 2.1. p[j-1] == "." : dp[i][j] = dp[i-1][j-1] 2.2 p[j-1] ==*:这是本题的难点 分两种讨论情况:首先给了 *，明白 * 的含义是 匹配零个或多个前面的那一个元素，所以要考虑他前面的元素即p的第j个元素前面一个元素j-1 为p[j-2]。*跟着他前一个字符走，前一个能匹配上 s的第i个元素s[i-1]，*才能有用，前一个都不能匹配上 s[i]，*也无能为力，只能让前一个字符消失，也就是匹配 0次前一个字符。
就2.2进行扩展： 1、p[j-2] != s[i-1] : dp[i][j] = dp[i][j-2] 这就是刚才说的那种前一个字符匹配不上的情况，*无能为力，只能让前一个字符即p[j-2]出现0次，比如ab与abc*(因为p[]会有. *符号，所以i和j并不相等) 2、p[j-1] == s[i] or p[j-1] == "." : dp[i][j]=dp[i][j-1] *前面那个字符，能匹配 s[i-1]，或者 * 前面那个字符是万能的 .比如 (##b , ###b *)，或者 ( ##b , ### . *) 只看 ### 后面一定是能够匹配上的，在这个例子中，##b中的b为s[i-1], ###b*, ###.*中的b/.为p[j-2]即第j-1个元素。所以要看 b 和 b *前面那部分 ##的地方匹不匹配还是看这位大佬的题解 事实证明，没有不会做的题，只有题解清不清晰的题。 在初始化这块，我卡了好久，对于空正则串p，非空字符串s的情况dp[i][0]=0, 这个i是s.size(), 我弄错成p的导致一直没有ac
class Solution{ public: bool isMatch(string s, string p){ //int m=s.size(),n=p.size(); //if(0==m || 0==n) return false; //s = " " + s; //p = " " + p; int m=s.size(),n=p.size(); vector<vector<bool>> dp(m+1, vector<bool>(n+1, false)); //int dp[m+1][n+1]; // base case dp[0][0]=true; // " "与" "匹配 // 空正则初始化 // dp[i][0]全为0， 非空串s与空正则串p肯定不匹配 for(int i = 1; i <= m; i++){ dp[i][0]=false; } // 空串/非空串s与非空正则p进行状态转移 for(int i=0;i<=m;i++){ for(int j=1;j<=n;j++){ //非空正则分为两种情况 * 和 非* if(p[j-1]!='*'){ if(i>0 && (s[i-1]==p[j-1] || p[j-1]=='.')){ dp[i][j]=dp[i-1][j-1]; }// else的情况已经默认为false了 } else{ // 碰到dp[j-1]=*号了, 分为看和不看两种情况 // 不看 if(j>=2){ dp[i][j]= dp[i][j] || dp[i][j-2]; } // 看 if(i>=1 && j>=2 && (s[i-1]==p[j-2] || p[j-2]=='.')){ dp[i][j] = dp[i][j] || dp[i-1][j]; } } } } return dp[m][n]; } };主要思路: 官方题解
dp[i,j]: s的第i个字符s[i-1]与p的第j个字符p[j-1]的匹配情况
// 非空串与空正则串的情况 // 空串与非正则串的情况(也可根据放到实际的状态转移来求(for循环)，本题因为*能匹配空字符串，所以可以提前初始化)
