10. Regular Expression Matching
经典DP题目,比较复杂,需要多复习。
dp[i][j] 表示 s 下标0~i,p 下标0~j 是否能够匹配
dp[i-1][j-1] s[i]==p[j] || p[j]=='.'
dp[i][j] = dp[i][j-2] p[j]=='*', 0 occurence
dp[i-1][j] p[j]=='*', s[i]==p[j-1] || p[j-1]=='.'
第一行是 p[j]!='*'的情况;后两行是p[j]=='*'的情况
dp[s.size()-1][p.size()-1] 为所求
为了方便,把dp[i][j]定义换为 s的前i个字符,p的前j个字符,设置dp[0][0] = true,可以方便base case的初始化。需要注意下标的对应。
base case 需要初始化所有 dp[i][0] 和 dp[0][j],其中dp[i][0] 都是false不用管,dp[0][j]不一定,利用dp[0][0]=ture初始化,和计算dp时写在一起。
写的时候注意下标要合法,dp[i][j] 中的 i, j 都要≥0,字符串的下标也要≥0。
p[j-1]!='*'时 dp[i][j] = dp[i-1][j-1] && (s[i-1]==p[j-1] || p[j-1]=='.') 的条件为 i≥1,j≥1
p[j-1]=='*',大前提是*前面还有一个字符,因此 j-1≥1 -> j≥2
dp[i][j] = dp[i][j-2] 要求 i≥0,这里当i=0时,就是在初始化dp[0][j]的base case
dp[i][j] = dp[i-1][j] && (s[i-1]==p[j-2] || p[j-2]=='.') 要求i≥1
class Solution {public: bool isMatch(string s, string p) { vector> dp(s.size()+1, vector (p.size()+1, false)); dp[0][0] = true; for (int i=0;i<=s.size();++i){ for (int j=1;j<=p.size();++j){ if (j>=2 && p[j-1]=='*'){ dp[i][j] = dp[i][j-2] || i>=1 && dp[i-1][j] && (s[i-1]==p[j-2] || p[j-2]=='.'); }else{ dp[i][j] = i>=1 && dp[i-1][j-1] && (s[i-1]==p[j-1] || p[j-1]=='.'); } } } return dp[s.size()][p.size()]; }};
44. Wildcard Matching
几乎和正则匹配一样,除了这里的 "*" 是不需要前面有一个字符的,写起来实际比正则匹配更容易。
同样把 dp[0][j] 的初始化写在了更新dp的里面。
class Solution {public: bool isMatch(string s, string p) { vector> dp(s.size()+1, vector (p.size()+1, false)); dp[0][0] = true; for (int i=0;i<=s.size();++i){ for (int j=1;j<=p.size();++j){ if (p[j-1]=='*') dp[i][j] = dp[i][j-1] || i>=1 && dp[i-1][j]; else dp[i][j] = i>=1 && dp[i-1][j-1] && (s[i-1]==p[j-1] || p[j-1]=='?'); } } return dp[s.size()][p.size()]; }};