题目描述
请实现一个函数用来匹配包括’.’和’*’的正则表达式。
模式中的字符’.’表示任意一个字符,而’*’表示它前面的字符可以出现任意次(含0次)。
在本题中,匹配是指字符串的所有字符匹配整个模式。
例如,字符串”aaa”与模式”a.a”和”abaca”匹配,但是与”aa.a”和”ab*a”均不匹配。
样例
输入:
s="aa"
p="a*"
输出:true
算法
动态规划
dp[i][j]=true表示的是A的前i个字符和B的前j个字符相匹配
我们考虑就一共有三种情况
1、a[i],b[j]都是字母并且a[i]==b[j],所以dp[i][j]=dp[i-1][j-1]
2、b[j]是’.’,只能匹配一个任意字符,dp[i][j]=dp[i-1][j-1];
3、b[j]是‘’,可以匹配0个或任意个字母,
(1) 0个的时候:dp[i][j]=dp[i][j-2];
(2) 任意个的时候: 1个:dp[i][j]=dp[i-1][j-2] 2个:dp[i-2][j-2] 3个: dp[i-3][j-2]
我们发现这样算太麻烦,只需要匹配a的第i个字母,匹配的上,再匹配i-1, 所以dp[i][j]=dp[i-1][j]
注意这里0个和任意个,并不是if else的关系,它是这两种情况中只要有一种成功,都算匹配成功
Java 代码
class Solution {
public boolean isMatch(String A, String B) {
int n = A.length();
int m = B.length();
boolean[][] dp = new boolean[n + 1][m + 1];
//因为前面存在j-1 i-1这些,所以在操作的时候,使用i-1 j-1操作串中的第i j个字符
dp[0][0]=true;
for (int i=0;i<=n;i++) {
for (int j=0;j<=m;j++) {
if (i>0&&j>0&&(A.charAt(i-1)==B.charAt(j-1)||B.charAt(j-1)=='.')) {
dp[i][j]=dp[i-1][j-1];
}else{
/*这里加B.charAt(j-2)=='.'条件是为了.*这种情况的出现*/
if (i >= 1 && j >= 2 && (A.charAt(i - 1) == B.charAt(j - 2)||B.charAt(j-2)=='.')) {
dp[i][j] |= dp[i - 1][j];
}
if (j >= 2) {
dp[i][j] |= dp[i][j - 2];
}
}
}
}
return dp[n][m];
}
}