[编程题]正则表达式匹配
==================================递归的2种方================================
===========================公共代码部分====================================
public static boolean match(char[] str, char[] pattern)
{
if(str == null || pattern == null)
return false;
return match(str, 0, pattern, 0);
} 版本1：这里是剑指offer的解题思路
/* 讨论2种：先看 * 再看 匹配* 前提：当pattern遍历完，return取决于str是否遍历完，str恰好遍历完才返回true，再接下来讨论
* 1.若当前字符存在下一个字符，看下一个字符是否是 '*'，如果是，有2种情况
* 一：当前匹配
* 1.1match(str,i + 1,pattern,j)//跳过str
* 1.2match(str,i,pattern,j + 2)//跳过pattern
* 1.3match(str,i + 1,pattern,j + 2)//这一种可以省略，相当于 1.1 + 1.2
* 二：当前不匹配
* match(str,i,pattern,j + 2)//跳过pattern
* 2.下一个不是 *
* 当前匹配 return match(str,i + 1,pattern,j + 1)
*/
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;
}
//这里是第二个思路， 反过来，先看匹配 ，再看 *
/*前提：当pattern遍历完，return取决于str是否遍历完，再接下来讨论
* 1.先看当前字符是否匹配 记录first_isMatch
* 2.再看下一个字符是否为 '*'
* 2.1当前匹配first_isMatch && match(str,i + 1,pattern,j)
* 2.2无论匹配与否match(str,i,pattern,j + 2)//跳过
* 3.不匹配*，当前字符匹配的前提下，进入到下一个循环
* else first_isMatch && match(str,i + 1,pattern,j + 1)
*/
/*前提：当pattern遍历完，return取决于str是否遍历完，再接下来讨论
* 1.先看当前字符是否匹配 记录first_isMatch
* 2.再看下一个字符是否为 '*'
* 2.1当前匹配first_isMatch && match(str,i + 1,pattern,j)
* 2.2无论匹配与否match(str,i,pattern,j + 2)//跳过
* 3.不匹配*，当前字符匹配的前提下，进入到下一个循环
* else first_isMatch && match(str,i + 1,pattern,j + 1)
*/
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种方法============================// //公共部分
/*
* 有了前面的认识，我们考虑用动态规划解题，动态规划有正向的和反向的，到底怎么取呢？
* 看下前面的递归调用：match1(str, i + 1, pattern, j + 1)相当于 dp[i][j]=dp[i+1][j+1]
* 适合反向遍历，于是，我们可以初始化boolean dp[len1+1][len2+1] 其中len1=str.length,len2=pattern.length
* 初始化dp[len1][len2]=true,含义是：str=aaa 和pattern=aa* 从末尾开始匹配 "" 和 "" 一定为true
* 这个时候开始循环
* 1.外循环：因为我们要用aa*匹配aaa,以aaa为外循环,注意，从""开始匹配接下来a,aa,aaa
* for(int i = len1;i>=0;i--)
* 2.内循环：拿aa*取匹配：匹配顺序 "*" "a*" "aa*",于是
* for(int j = len2 - 1;j>=0;j--)
* 循环体内部逻辑，参考递归调用：
* ============= *版本1：=============
* 先看下一个是否是“*”，再看当前是否相等
* 1.若下一个是"*",分为当前相等和当前不等
* 1.1：当前相等dp[i][j]=dp[i][j+2] || dp[i+1][j]
* 1.2：当前不等dp[i][j]=dp[i][j+2]
* 2.若不是"*",但是当前相等 d[i][j]= dp[i + 1][j + 1];
* 有了前面的认识，我们考虑用动态规划解题，动态规划有正向的和反向的，到底怎么取呢？
* 看下前面的递归调用：match1(str, i + 1, pattern, j + 1)相当于 dp[i][j]=dp[i+1][j+1]
* 适合反向遍历，于是，我们可以初始化boolean dp[len1+1][len2+1] 其中len1=str.length,len2=pattern.length
* 初始化dp[len1][len2]=true,含义是：str=aaa 和pattern=aa* 从末尾开始匹配 "" 和 "" 一定为true
* 这个时候开始循环
* 1.外循环：因为我们要用aa*匹配aaa,以aaa为外循环,注意，从""开始匹配接下来a,aa,aaa
* for(int i = len1;i>=0;i--)
* 2.内循环：拿aa*取匹配：匹配顺序 "*" "a*" "aa*",于是
* for(int j = len2 - 1;j>=0;j--)
* 循环体内部逻辑，参考递归调用：
* ============= *版本1：=============
* 先看下一个是否是“*”，再看当前是否相等
* 1.若下一个是"*",分为当前相等和当前不等
* 1.1：当前相等dp[i][j]=dp[i][j+2] || dp[i+1][j]
* 1.2：当前不等dp[i][j]=dp[i][j+2]
* 2.若不是"*",但是当前相等 d[i][j]= dp[i + 1][j + 1];
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.===============* 先看当前是否相等，再看下一个是否为“*”
* 1.当前相等 立一个flag：
* first_isMatch=i != str.length && (str[i] == pattern[j] || pattern[j] == '.')
* 2.下一个是“*”
* 无论当前是否相等，都可以跳过dp[i][j]=dp[i][j+2] ||
* 或者，当前相等，那么 dp[i][j] = (first_isMatch && dp[i+1][j])
* 综合得： dp[i][j] = dp[i][j+2] ||(first_isMatch && dp[i+1][j]);
* 3.return dp[0][0]遍历完成
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];
}
发表于 2018-06-13 11:19:48
回复(23)
/*
思路：只有当模式串和字符串同时等于\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;
}
};
编辑于 2016-09-09 16:27:24
回复(22)
动态规划
如果 pattern[j] == str[i] || pattern[j] == '.', 此时dp[i][j] = dp[i-1][j-1];
如果 pattern[j] == '*'
分两种情况:
1: 如果pattern[j-1] != str[i] && pattern[j-1] != '.',
此时dp[i][j] = dp[i][j-2] //a*匹配0次
2: 如果pattern[j-1] == str[i] || pattern[j-1] == '.'
此时dp[i][j] = dp[i][j-2] // a*匹配0次
或者 dp[i][j] = dp[i][j-1] // a*匹配1次
或者 dp[i][j] = dp[i-1][j] // a*匹配多次
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];
}
}
编辑于 2017-04-26 15:16:13
回复(11)
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;
}
发表于 2016-04-09 13:27:31
回复(2)
/*
要分为几种情况：（状态机）
（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);
}
}
};
发表于 2017-06-19 19:46:21
回复(4)
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;
}
发表于 2015-08-20 14:17:37
回复(15)
//递归的思想
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;
}
}
发表于 2015-06-21 22:15:56
回复(0)
分析：递归实现
每次分别在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;
}
发表于 2015-09-01 19:34:25
回复(2)
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);
}
};
编辑于 2017-06-23 15:53:37
回复(6)
看到一堆指数级的回答,,还有题目都没说 .*
是.的意义可以重复多次还是同一个字符重复多次（也就是.*能不能匹配abcdef），虽然我猜根本没有这种数据（hehe）
f(a, b) 表示s[a..n]和p[b..m]的匹配结果，枚举一个可匹配的前缀进行转移，记忆化避免重复计算。O(n^2)
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);
}
};
编辑于 2016-01-02 20:36:14
回复(2)
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];
}
};
发表于 2018-01-23 11:33:47
回复(0)
//回溯法
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;
}
}
发表于 2017-05-09 04:21:02
回复(0)
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;
}
编辑于 2017-04-03 17:50:46
回复(2)
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);
}
};
发表于 2016-06-03 19:35:05
回复(0)
当模式中的第二个字符不是“*”时：
1、如果字符串第一个字符和模式中的第一个字符相匹配，那么字符串和模式都后移一个字符，然后匹配剩余的。
2、如果
字符串第一个字符和模式中的第一个字符相不匹配，直接返回false。
而当模式中的第二个字符是“*”时：
如果字符串第一个字符跟模式第一个字符不匹配，则模式后移2个字符，继续匹配。如果字符串第一个字符跟模式第一个字符匹配，可以有3种匹配方式：
1、模式后移2字符，相当于x*被忽略；
2、字符串后移1字符，模式后移2字符；
3、字符串后移1字符，模式不变，即继续匹配字符下一位，因为*可以匹配多位；
这里需要注意的是：Java里，要时刻检验数组是否越界。
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;
}
}
编辑于 2016-07-21 19:23:43
回复(114)
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);
}
}
};
发表于 2020-02-09 10:51:50
回复(0)
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;
}
}
发表于 2019-10-20 18:00:36
回复(0)
问题信息
难度：
467条回答
2693收藏
116778浏览
通过挑战的用户
-
2023-03-12 18:00:20 -
2023-03-06 15:43:59 -
2022-10-28 19:58:00
-
2022-10-27 10:43:52
-
2022-10-19 18:30:30
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
