首页 > 试题广场 >

正则表达式匹配

[编程题]正则表达式匹配
  • 热度指数:398596 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 128M,其他语言256M
  • 算法知识视频讲解
请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符,而'*'表示它前面的字符可以出现任意次(包含0次)。 在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串"aaa"与模式"a.a"和"ab*ac*a"匹配,但是与"aa.a"和"ab*a"均不匹配
示例1

输入

"aaa","a*a"

输出

true
==================================递归的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)
     */
 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];
 

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)
/**
这样写会被打的
*/
    public boolean match(char[] str, char[] pattern)
    {
        return  new String(str).matches(new String(pattern));
    }
发表于 2016-09-19 18:09:21 回复(13)
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)
看到那么多答案要么抄剑指offer,要么互相抄袭,我就放心了
发表于 2017-04-20 20:20:56 回复(1)
看到一堆指数级的回答,,还有题目都没说 .* 是.的意义可以重复多次还是同一个字符重复多次(也就是.*能不能匹配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 boolean match(char[] str, char[] pattern)
    {
        String regex = String.valueOf(pattern);
        String s = String.valueOf(str);
        return s.matches(regex);
    }

发表于 2017-07-14 10:57:24 回复(4)
//回溯法
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)