【LeetCode】Day126-正则表达式匹配
题目
10. 正则表达式匹配【困难】
题解
用字符串匹配纠结了半天，结果解法是用动态规划，果然还是我太天真了
对于 p 中一个字符而言，它只能在 s 中匹配一个字符，匹配的方法具有唯一性；而对于 p 中字符 + 星号的组合而言，它可以在 s 中匹配任意自然数个字符，并不具有唯一性。因此我们可以考虑使用动态规划，对匹配的方案进行枚举。
官解说的云里雾里，个人感觉这篇题解「手画图解」动态规划，需要仔细的分情况讨论说的特别好，有图，分析也比较细致
-
状态定义：dp[i][j] 表示s[0…i-1]与p[0…j-1]是否能够匹配。
-
状态转移方程：本题最复杂的地方，关键是对于星号的讨论，p[j-1]星号可以让p[j-2]在s串中消失、重复一次、重复>=2次
-
初始条件：dp[0][0]=true，表示两个空字符串可以匹配上
-
返回值：dp[m][n]
class Solution {
public boolean isMatch(String s, String p) {
int m=s.length(),n=p.length();
boolean[][] dp=new boolean[m+1][n+1];
dp[0][0]=true;
for(int i=0;i<=m;i++){
for(int j=1;j<=n;j++){
if(p.charAt(j-1)=='*'){
dp[i][j]=dp[i][j-2];//无论p[j-2]是啥,都能被*消掉,因此dp[i][j]和dp[i][j-2]值相等
//若s[i-1]和p[j-2]匹配上,说明s[i-1]重复了多次
if(match(s,p,i,j-1)){
dp[i][j]=dp[i-1][j] || dp[i][j-2];
}
}
else{
//两个字母匹配上了或者和"."匹配上了
if(match(s,p,i,j)){
dp[i][j]=dp[i-1][j-1];
}
}
}
}
return dp[m][n];
}
public boolean match(String s,String p,int i,int j){
if(i==0)
return false;
if(p.charAt(j-1)=='.')
return true;
return s.charAt(i-1)==p.charAt(j-1);
}
}
时间复杂度： O ( m n ) O(mn) O(mn)
空间复杂度： O ( m n ) O(mn) O(mn)