题目描述
给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。
’.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素
所谓匹配,是要涵盖 整个 字符串 s的,而不是部分字符串。
代码
class Solution {
public boolean isMatch(String s, String p) {
int n = s.length(), m = p.length();
char[] a = (" "+s).toCharArray(), b = (" "+p).toCharArray();
boolean[][] f = new boolean[n+5][m+5]; //f[i][j]表示1~i的s和1~j的p是否能匹配
//初始化
f[0][0] = true;
for(int j=2; j<=m; j++){
if(b[j]=='*') f[0][j] = f[0][j-2]; //因为a*可以表示0个a
}
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
if(b[j]=='*'){
f[i][j] |= f[i][j-2]; //b[j-1]*不匹配的情况
//b[j-1]*至少匹配一个a[i]
if(b[j-1]==a[i] || b[j-1]=='.') f[i][j] |= f[i-1][j];
}else{
if(b[j]==a[i] || b[j]=='.') f[i][j] |= f[i-1][j-1];
}
}
}
return f[n][m];
}
}