10. 正则表达式匹配
1.动态规划
public boolean isMatch(String s, String p) {
char[] cs = s.toCharArray();
char[] cp = p.toCharArray();
// dp[i][j]:表示s的前i个字符,p的前j个字符是否能够匹配
boolean[][] dp = new boolean[cs.length + 1][cp.length + 1];
// 初期值
// s为空,p为空,能匹配上
dp[0][0] = true;
// p为空,s不为空,必为false(boolean数组默认值为false,无需处理)
// s为空,p不为空,由于*可以匹配0个字符,所以有可能为true
for (int j = 1; j <= cp.length; j++) {
if (cp[j - 1] == '*') {
dp[0][j] = dp[0][j - 2];
}
}
// 填格子
for (int i = 1; i <= cs.length; i++) {
for (int j = 1; j <= cp.length; j++) {
// 文本串和模式串末位字符能匹配上
if (cs[i - 1] == cp[j - 1] || cp[j - 1] == '.') {
dp[i][j] = dp[i - 1][j - 1];
} else if (cp[j - 1] == '*') { // 模式串末位是*
// 模式串*的前一个字符能够跟文本串的末位匹配上
if (cs[i - 1] == cp[j - 2] || cp[j - 2] == '.') {
dp[i][j] = dp[i][j - 2] // *匹配0次的情况
|| dp[i - 1][j]; // *匹配1次或多次的情况
} else { // 模式串*的前一个字符不能够跟文本串的末位匹配
dp[i][j] = dp[i][j - 2]; // *只能匹配0次
}
}
}
}
return dp[cs.length][cp.length];
}
2.递归
// 递归写法
public boolean isMatch(String s, String p){
if (s.length()==0 ){
if (p.length()==0){
return true;
}
if (p.charAt(p.length()-1)!='*'){
return false;
}else{
return isMatch(s,p.substring(0,p.length()-2));
}
}else if(p.length()== 0){
return false;
}
if(s.charAt(s.length()-1) == p.charAt(p.length()-1) || p.charAt(p.length()-1) == '.'){
return isMatch(s.substring(0,s.length()-1),p.substring(0,p.length()-1));
}else if(p.charAt(p.length()-1) == '*'){
if(s.charAt(s.length()-1) == p.charAt(p.length()-2) || p.charAt(p.length()-2) == '.'){
return isMatch(s,p.substring(0,p.length()-2)) || isMatch(s.substring(0,s.length()-1),p.substring(0,p.length()-2)) || isMatch(s.substring(0,s.length()-1),p);
}else{
return isMatch(s,p.substring(0,p.length()-2));
}
}else{
return false;
}
}
思路:
{{uploading-image-753426.png(uploading...)}}
转载:https://leetcode.cn/problems/regular-expression-matching/solutions/296114/shou-hui-tu-jie-wo-tai-nan-liao-by-hyj8/
参考:https://www.bilibili.com/video/BV1jd4y1U7kE/?spm_id_from=333.337.search-card.all.click&vd_source=136c403361d2786d99be256b33ac445a