public static boolean match(char[] str, char[] pattern) { if(str == null || pattern == null) return false; return match(str, 0, pattern, 0); }
private boolean match(char[] str, int i, char[] pattern, int j) { if(j == pattern.length)//pattern遍历完了 return str.length == i;//如果str也完了,返回true,不然false //注意数组越界问题,一下情况都保证数组不越界 if(j < pattern.length - 1 && pattern[j + 1] == '*') {//下一个是* if(str.length != i && //当前匹配 (str[i] == pattern[j] || pattern[j] == '.')) //匹配 return match(str,i,pattern,j + 2) || match(str,i + 1,pattern,j); else//当前不匹配 return match(str,i,pattern,j + 2); } //下一个不是“*”,当前匹配 if(str.length != i && (str[i] == pattern[j] || pattern[j] == '.')) return match(str,i + 1,pattern,j + 1); return false; }
private boolean match1(char[] str, int i, char[] pattern, int j) { if(j == pattern.length)//pattern遍历完了 return str.length == i;//如果str也完了,返回true,不然false //1.先看当前是否匹配 boolean first_isMatch = (i != str.length) && (str[i] == pattern[j] || pattern[j] == '.'); //2.再看后面是否有* pattern[j + 1] == '*' if(j < pattern.length - 1 && pattern[j + 1] == '*') { return match1(str, i, pattern, j + 2) || (first_isMatch && match1(str, i + 1, pattern, j)); }else { return first_isMatch && match1(str, i + 1, pattern, j + 1); } }//===========================下面是动态规划的2种方法============================//
public static boolean matchDP1(char[] str, char[] pattern) { if(str == null || pattern == null) return false; boolean [][] dp = new boolean[str.length + 1][pattern.length + 1]; dp[str.length][pattern.length] = true; //开始循环 for (int i = str.length; i >= 0; i--) {//外循环:从空串开始匹配 for (int j = pattern.length - 1; j >= 0; j--) {//内循环:从最后一个字符开始匹配 if(j < pattern.length - 1 && pattern[j + 1] == '*') { //1.1:当前相等 if(i < str.length && (str[i] == pattern[j] || pattern[j] == '.')) dp[i][j] = dp[i][j + 2] || dp[i + 1][j]; else//1.2当前不等 dp[i][j] = dp[i][j + 2]; }else {//若不是"*",看当前是否相等 if(i != str.length && (str[i] == pattern[j] || pattern[j] == '.')) {//当前相等 dp[i][j] = dp[i + 1][j + 1]; } } } } return dp[0][0]; }* ============ *版本2.===============
public static boolean matchDP2(char[] str, char[] pattern) { if(str == null || pattern == null) return false; boolean [][] dp = new boolean[str.length + 1][pattern.length + 1]; dp[str.length][pattern.length] = true; //开始循环 for (int i = str.length; i >= 0; i--) {//外循环:从空串开始匹配 for (int j = pattern.length - 1; j >= 0; j--) {//内循环:从最后一个字符开始匹配 //1.当前相等 立一个flag:相当于把if判断抽取出来,简化代码first_isMatch boolean first_isMatch = (i != str.length) && (str[i] == pattern[j] || pattern[j] == '.'); //2.下一个是“*” if(j < pattern.length - 1 && pattern[j + 1] == '*') { dp[i][j] = dp[i][j + 2] || ( first_isMatch && dp[i + 1][j]); }else { dp[i][j] = first_isMatch && dp[i + 1][j + 1]; } } } return dp[0][0]; }
/*
思路:只有当模式串和字符串同时等于\0,才可以认为两个串匹配。
在匹配中,对于每个位的匹配可以分为三种情况
1、(相应位匹配||模式串为.&&字符串不是\0)&&模式串下一位是*
2、(相应位匹配||模式串为.&&字符串不是\0)&&模式串下一位不是*
3、相应位不匹配&&(模式位不为.||字符串是\0)
对应1,最复杂。分为*取0,*取1,*>=2三种情况。
*取0对应跳过当前匹配位,继续寻找patter的下一个匹配位,str不变,pattern+2
*取1对应当前匹配位算一次成功匹配,str+1,pattern+2
*取>=2对应一次成功匹配,继续匹配字符串的下一位是否匹配,str+1,pattern不变
三者取或。即只要有一种情况能匹配成功认为字符串就是匹配成功的。
对应2,相当于一次成功匹配,str+1,pattern+1
对应3,匹配失败,直接返回false
*/
class Solution {
public:
bool match(string str, string pattern) {
char a[100],b[100];
strcpy(a,str.c_str());
strcpy(b,pattern.c_str());
return match(a, b);
}
bool match(char* str, char* pattern)
{
if(str==NULL||pattern==NULL)
return false;
return matchCore(str,pattern);
}
bool matchCore(char* str, char* pattern)
{
if(*str=='\0'&&*pattern=='\0')
return true;
if(*str!='\0'&&*pattern=='\0')
return false;
if(*(pattern+1)=='*')
{
if(*pattern==*str||(*pattern=='.'&&*str!='\0'))
/*
matchCore(str,pattern+2):模式串未匹配
matchCore(str+1,pattern):模式串已经匹配成功,尝试匹配下一个字符串
matchCore(str+1,pat+2):模式串已经成功匹配,并且不匹配下一个字符串内容 注意这里 matchCore(str+1,pat+2)重复考虑了(代码中已经去除),谢谢@chlq的指出 */
return matchCore(str+1,pattern)||matchCore(str,pattern+2);
else
return matchCore(str,pattern+2);
}
if(*str==*pattern||(*pattern=='.'&&*str!='\0'))
return matchCore(str+1,pattern+1);
return false;
}
};
public class Solution { public boolean match(char[] str, char[] pattern) { boolean[][] dp = new boolean[str.length + 1][pattern.length + 1]; dp[0][0] = true; for (int i = 1; i < dp[0].length; i ++) { if(pattern[i - 1] == '*') dp[0][i] = dp[0][i - 2]; } for (int i = 1; i < dp.length; i ++) { for (int j = 1; j < dp[0].length; j ++) { if(pattern[j - 1] == '.' || pattern[j - 1] == str[i - 1]) dp[i][j] = dp[i - 1][j - 1]; else if(pattern[j - 1] == '*') { if(pattern[j - 2] != str[i - 1] && pattern[j - 2] != '.') dp[i][j] = dp[i][j - 2]; else dp[i][j] = dp[i][j - 1] || dp[i][j - 2] || dp[i - 1][j]; } } } return dp[str.length][pattern.length]; } }
public boolean match(char[] str, char[] pattern) { if (str == null || pattern == null) { return false; } int strIndex = 0; int patternIndex = 0; return matchCore(str, strIndex, pattern, patternIndex); } public boolean matchCore(char[] str, int strIndex, char[] pattern, int patternIndex) { //str到尾,pattern到尾,匹配成功 if (strIndex == str.length && patternIndex == pattern.length) { return true; } //str未到尾,pattern到尾,匹配失败 if (strIndex != str.length && patternIndex == pattern.length) { return false; } //str到尾,pattern未到尾(不一定匹配失败,因为a*可以匹配0个字符) if (strIndex == str.length && patternIndex != pattern.length) { //只有pattern剩下的部分类似a*b*c*的形式,才匹配成功 if (patternIndex + 1 < pattern.length && pattern[patternIndex + 1] == '*') { return matchCore(str, strIndex, pattern, patternIndex + 2); } return false; } //str未到尾,pattern未到尾 if (patternIndex + 1 < pattern.length && pattern[patternIndex + 1] == '*') { if (pattern[patternIndex] == str[strIndex] || (pattern[patternIndex] == '.' && strIndex != str.length)) { return matchCore(str, strIndex, pattern, patternIndex + 2)//*匹配0个,跳过 || matchCore(str, strIndex + 1, pattern, patternIndex + 2)//*匹配1个,跳过 || matchCore(str, strIndex + 1, pattern, patternIndex);//*匹配1个,再匹配str中的下一个 } else { //直接跳过*(*匹配到0个) return matchCore(str, strIndex, pattern, patternIndex + 2); } } if (pattern[patternIndex] == str[strIndex] || (pattern[patternIndex] == '.' && strIndex != str.length)) { return matchCore(str, strIndex + 1, pattern, patternIndex + 1); } return false; }
/* 要分为几种情况:(状态机) (1)当第二个字符不为‘*’时:匹配就是将字符串和模式的指针都下移一个,不匹配就直接返回false (2)当第二个字符为'*'时: 匹配: a.字符串下移一个,模式不动 b.字符串下移一个,模式下移两个 c.字符串不动,模式下移两个 不匹配:字符串下移不动,模式下移两个 搞清楚这几种状态后,用递归实现即可: */ class Solution { public: bool match(string str, string pattern) { char a[100],b[100]; strcpy(a,str.c_str()); strcpy(b,pattern.c_str()); return match(a, b); } bool match(char* str, char* pattern){ if(str[0]=='\0'&&pattern[0]=='\0') return true; else if(str[0]!='\0'&&pattern[0]=='\0') return false; if(pattern[1]!='*'){ if(str[0]==pattern[0]||(pattern[0]=='.'&&str[0]!='\0')) return match(str+1,pattern+1); else return false; } else{ if(str[0]==pattern[0]||(pattern[0]=='.'&&str[0]!='\0')) return match(str,pattern+2)||match(str+1,pattern)||match(str+1,pattern+2); else return match(str,pattern+2); } } };
bool match(string str, string pattern) { char a[100],b[100]; strcpy(a,str.c_str()); strcpy(b,pattern.c_str()); return match(a, b); } bool match(char* str, char* pattern) { if (pattern[0] == 0 && str[0] == 0) { return true; } if (pattern[0] != 0 && pattern[1] == '*') { if (match(str, pattern + 2)) return true; } if ((pattern[0] == '.' && str[0]) || str[0] == pattern[0]) { if (match(str + 1, pattern + 1)) return true; if (pattern[1] == '*' && match(str + 1, pattern)) { return true; } } return false; }
//递归的思想 public class Solution { boolean match(char[] str, char[] pattern) { return isMatch(str,0,pattern,0); } public boolean isMatch(char[] str,int start1,char[] pattern,int start2){ if(start1==str.length&&start2==pattern.length) return true; if(start2>=pattern.length) return false; if(start2<pattern.length-1){ if(pattern[start2+1]=='*'){ if((start1<str.length)&&(str[start1]==pattern[start2]||pattern[start2]=='.')){ return isMatch(str,start1,pattern,start2+2)||isMatch(str,start1+1,pattern,start2+2)||isMatch(str,start1+1,pattern,start2); }else return isMatch(str,start1,pattern,start2+2); } } if(start1==str.length) return false; if(str[start1]==pattern[start2]||pattern[start2]=='.') return isMatch(str,start1+1,pattern,start2+1); return false; } }
分析:递归实现 每次分别在str 和pattern中取一个字符进行匹配,如果匹配,则匹配下一个字符,否则,返回不匹配。 设匹配递归函数 match(str, pattern)。 如果模式匹配字符的下一个字符是‘*’: •如果pttern当前字符和str的当前字符匹配,:有以下三种可能情况 (1)pttern当前字符能匹配 str 中的 0 个字符:match(str, pattern+2) (2)pttern当前字符能匹配 str 中的 1 个字符:match(str+1, pattern+2) (3)pttern当前字符能匹配 str 中的 多 个字符:match(str+1, pattern) •如果pttern当前字符和和str的当前字符不匹配 pttern当前字符能匹配 str 中的 0 个字符:(str, pattern+2) 如果模式匹配字符的下一个字符不是‘*’,进行逐字符匹配。 对于 ‘.’ 的情况比较简单,’.’ 和一个字符匹配 match(str+1, pattern+1) 另外需要注意的是:空字符串”” 和 “.*” 是匹配的 bool match(string str, string pattern) { char a[100],b[100]; strcpy(a,str.c_str()); strcpy(b,pattern.c_str()); return match(a, b); } bool match(char* str, char* pattern) { if(str==NULL||pattern==NULL) return false; if(*str=='\0') { if(*pattern=='\0'||*(pattern+1)=='*'&&(pattern+2)=='\0') return true; else return false; } if(*pattern=='\0') return false; if(*(pattern+1)=='*') { if(*pattern==*str||*pattern=='.') { return match(str,pattern+2)||match(str+1,pattern); } else return match(str,pattern+2); } if(*pattern==*str||*pattern=='.') return match(str+1,pattern+1); return false; }
class Solution { public: bool match(char* s, char* p) { if (!s || !p) return false; if (!*p) return !*s; if (*(p + 1) == '*') return match(s, p + 2) || (*s == *p || *s && *p == '.') && match(s + 1, p); return (*s == *p || *s && *p == '.') && match(s + 1, p + 1); } };
class Solution { char *s, *p; int n, m; char f[1000][1000]; //此处本应是动态申请f[n + 1][m + 1],为了方便简洁就算了 char judge(int a, int b){ if(a > n || b > m) return 0; if(~f[a][b]) return f[a][b]; char &ret = f[a][b]; if(a == n && b == m) return ret = 1; if(p[b + 1] != '*'){ if(p[b] == '.' || s[a] == p[b]) return ret = judge(a + 1, b + 1); else return ret = 0; } else{ for(int i = a; i <= n; ++i){ if(judge(i, b + 2)) return ret = 1; if(s[i] != p[b] && p[b] != '.') return ret = 0; } return ret = 0; } } public: bool match(string str, string pattern) { char a[100],b[100]; strcpy(a,str.c_str()); strcpy(b,pattern.c_str()); return match(a, b); } bool match(char* str, char* pat){ s = str, n = strlen(s); p = pat, m = strlen(p); memset(f, 0xff, sizeof f); return judge(0, 0); } };
class Solution { public: bool match(char* s, char* p) { int slen = strlen(s), plen = strlen(p); // dp[i+1][k+1] tells if s[:i] matches p[:k] ... vector<vector<bool>> dp(slen+1, vector<bool>(plen+1, false)); dp[0][0] = true; for(int k=0; k < plen; ++k) { if(p[k] == '*') { dp[0][k+1] = dp[0][k-1]; } } for(int i=0; i < slen; ++i) { for(int k=0; k < plen; ++k) { if(p[k]=='.' || s[i]==p[k]) { dp[i+1][k+1] = dp[i][k]; } else if(p[k]=='*') { if(p[k-1]==s[i] || p[k-1]=='.') { dp[i+1][k+1] = dp[i+1][k-1] || dp[i+1][k] || dp[i][k+1]; } else { dp[i+1][k+1] = dp[i+1][k-1]; } } } } return dp[slen][plen]; } };
//回溯法 public class Solution { public boolean match(char[] str, char[] pattern){ return matchChar(str,pattern,0,0); } public boolean matchChar(char[] str, char[] pattern,int s,int p){ if(str==null||pattern==null) return false; if(s>=str.length&&p>=pattern.length) return true; if(s<str.length&&p>=pattern.length) return false; if((p+1)<pattern.length&&pattern[p+1]=='*'){ if(s<str.length&&(str[s]==pattern[p]||pattern[p]=='.')) return matchChar(str,pattern,s,p+2)||matchChar(str,pattern,s+1,p+2)||matchChar(str,pattern,s+1,p); else return matchChar(str,pattern,s,p+2); }else if(s<str.length&&(str[s]==pattern[p]||pattern[p]=='.')) return matchChar(str,pattern,s+1,p+1); else return false; } }
public boolean match(char[] str, char[] pattern){ // .* 匹配一切 if(pattern.length == 2 && pattern[0] == '.' && pattern[1] == '*') return true; // 两个序列入栈 Stack<Character> ori = new Stack<>(); Stack<Character> pat = new Stack<>(); for (int i = 0; i < str.length; i++) { ori.push(str[i]); } for (int i = 0; i < pattern.length; i++) { pat.push(pattern[i]); } // 从尾匹配,解决*重复前一个字符的问题 while (!ori.empty() && !pat.empty()){ // 如果是两个不相同的字母,匹配失败 if(Character.isLetter(pat.peek()) && !pat.peek().equals(ori.peek())) return false; // 两个相同的字母,匹配成功,两个栈顶各弹出已经匹配的字符 if(Character.isLetter(pat.peek()) && pat.peek().equals(ori.peek())){ ori.pop(); pat.pop(); }else if(pat.peek().equals('.')){ // 如果模式串是 ‘.’,直接把它替换为所需的字符入栈 pat.pop(); pat.push(ori.peek()); }else{ // 模式串是 * pat.pop(); if(pat.peek().equals(ori.peek())){ // *的下一个是目标字符,则重复它再重新压入* pat.push(ori.peek()); pat.push('*'); ori.pop(); }else{ // 否则从模式栈弹栈,直到找到匹配目标串的字符,或遇到. while (!pat.empty() && !pat.peek().equals(ori.peek()) && !pat.peek().equals('.')) pat.pop(); // 如果遇到了‘.’ 直接替换为目标字符,再重新压入* if(!pat.empty() && pat.peek() == '.'){ pat.pop(); pat.push(ori.peek()); pat.push('*'); } } } } // 两栈空,则匹配成功 if(ori.empty() && pat.empty()) return true; // 如果模式栈不空 // 仅当模式栈中的*可以‘吃掉’多余的字符时匹配成功 // 例如 aa* / aa*bb* ,而不可以是baa* if(ori.empty() && !pat.empty() && pat.peek().equals('*')){ char c = pat.pop(); while (!pat.empty()){ if(c == '*' || pat.peek() == '*' || c == pat.peek()) c = pat.pop(); else return false; } return true; } // 其他情况均不成功 return false; }
class Solution { public: bool match(string str, string pattern) { char a[100],b[100]; strcpy(a,str.c_str()); strcpy(b,pattern.c_str()); return match(a, b); } bool match(char* str, char* pattern) { //1.有效性检查 /* str不能有.* pattern模式中*前面必须有一个字符 */ //2.匹配情况 /*定义s[i]和p[i]表示从i位置到结尾的字符串 1) s[i],p[i]不相等时,而且P[i+1]!=*或者.,则return false 如果P[i+1]=*则s[i]与p[i+2]继续比较 2) s[i],p[i]相等时,如果p[i+1]=*,比如s=xxxxzzzz,p=x*yyyy 如果p[i+1]不等于*时,则i++ */ if(str==NULL||pattern==NULL) { return false; } for(int i=0;i<(int)strlen(str);i++) { if(str[i]=='.'||str[i]=='*') { return false; } } for(int i=0;i<(int)strlen(pattern);i++) { if(pattern[i]=='*'&&(i==0||pattern[i-1]=='*')) { return false; } } return expMatch(str,0,pattern,0); } bool expMatch(char* s,int si,char* p,int pi) { if(pi==(int)strlen(p)) { return si==(int)strlen(s); } //注意p只有两个字符而且没有*时,要求满足p[i]==s[i]而且si不能为最后一个字符 if(pi+1==(int)strlen(p)||p[pi+1]!='*') { return si!=(int)strlen(s)&&(s[si]==p[pi]||p[pi]=='.') &&expMatch(s,si+1,p,pi+1); } /* p[i+1]=*,s[i],p[i]相等时,比如s=xxxxzzzz,p=x*yyyy */ while(si!=(int)strlen(s)&&(s[si]==p[pi]||p[pi]=='.')) { if(expMatch(s,si,p,pi+2)) { return true; } si++; } return expMatch(s,si,p,pi+2); } };
public class Solution {
public boolean match(char[] str, char[] pattern) {
if (str == null || pattern == null) {
return false;
}
int strIndex = 0;
int patternIndex = 0;
return matchCore(str, strIndex, pattern, patternIndex);
}
public boolean matchCore(char[] str, int strIndex, char[] pattern, int patternIndex) {
//有效性检验:str到尾,pattern到尾,匹配成功
if (strIndex == str.length && patternIndex == pattern.length) {
return true;
}
//pattern先到尾,匹配失败
if (strIndex != str.length && patternIndex == pattern.length) {
return false;
}
//模式第2个是*,且字符串第1个跟模式第1个匹配,分3种匹配模式;如不匹配,模式后移2位
if (patternIndex + 1 < pattern.length && pattern[patternIndex + 1] == '*') {
if ((strIndex != str.length && pattern[patternIndex] == str[strIndex]) || (pattern[patternIndex] == '.' && strIndex != str.length)) {
return matchCore(str, strIndex, pattern, patternIndex + 2)//模式后移2,视为x*匹配0个字符
|| matchCore(str, strIndex + 1, pattern, patternIndex + 2)//视为模式匹配1个字符
|| matchCore(str, strIndex + 1, pattern, patternIndex);//*匹配1个,再匹配str中的下一个
} else {
return matchCore(str, strIndex, pattern, patternIndex + 2);
}
}
//模式第2个不是*,且字符串第1个跟模式第1个匹配,则都后移1位,否则直接返回false
if ((strIndex != str.length && pattern[patternIndex] == str[strIndex]) || (pattern[patternIndex] == '.' && strIndex != str.length)) {
return matchCore(str, strIndex + 1, pattern, patternIndex + 1);
}
return false;
}
}
class Solution { public: bool match(char* str, char* pattern) { if (*str == '\0' && *pattern == '\0') { return true; } if (*str != '\0' && *pattern == '\0') { return false; } if (*(pattern + 1) != '*') { if (*pattern == *str || (*pattern == '.' && *str != '\0')) { return match(str + 1, pattern + 1); }else return false; }else{//.*也可能存在 if (*pattern == *str || (*pattern == '.' && *str != '\0')) {//字符串走一步、或者多步,或者一步都不走 //这个或是,即使条件成立可能走也可能不走 return match(str + 1, pattern) || match(str, pattern + 2); }else//无论如何都要走 return match(str, pattern + 2); } } };
public class Solution { public boolean match(char[] str, char[] pattern){ if(str == null || pattern == null) return false; if(str.length == 0){ if(pattern.length == 0 || (pattern.length == 2 && pattern[1] == '*')){ return true; }else{ return false; } } if(pattern.length == 0)return false; int i = 0; int j = 0; while(i < str.length){ if(j == pattern.length - 1){ if(i == str.length - 1 && (str[i] == pattern[j] || pattern[j] == '.')){ return true; }else{ return false; } } if(j > pattern.length - 1) return false; if(pattern[j + 1] == '*'){ int index = i; // 记录回退数量,管理这样的"a*a"的匹配 int back = 0; int point = j + 1; while(++point <= pattern.length - 1 && ((index + 1 < str.length && str[index + 1] == pattern[j]) || index + 1 == str.length)){ if(pattern[point] == pattern[j]){ back++; if(point + 1 <= pattern.length - 1 && pattern[point] == '*')back--; } } // 单独处理"."的回退问题 while(++point <= pattern.length - 1 && pattern[j] == '.'){ back++; if(point + 1 <= pattern.length - 1 && pattern[point] == '*')back--; } while(index < str.length && (str[index] == pattern[j] || pattern[j] == '.')){ index++; } index-=back; if(index == str.length && j + 1 == pattern.length - 1)return true; if(j + 1 == pattern.length - 1)return false; if(index == str.length)return false; j+=2; i = index; }else{ if(str[i] != pattern[j] && pattern[j] != '.')return false; i++; j++; } } if(j + 1 == pattern.length - 1 && pattern[j + 1] == '*')return true; return false; } }