正则表达式匹配_

JacobGo！

/* 
 * 
 * 动态规划DP的应用 
 * Runtime: 29 ms.Your runtime beats 81.88 % of java submissions.
 */
public class Demo1 {
	/*
	 * 如果对动态规划不太了解，可以参考博客：http://blog.csdn.net/zjkc050818/article/details/74532023  * 以及博客中的视频。
	 */
	public boolean isMatch(String s, String p) {
		if (s == null || p == null)
			return false;
		int m = s.length(), n = p.length();
		boolean[][] res = new boolean[m + 1][n + 1];
		res[0][0] = true;
		for (int i = 0; i < n; i++) {
			if (p.charAt(i) == '*' && res[0][i - 1])
				res[0][i + 1] = true;
		}
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (p.charAt(j) == '.')
					res[i + 1][j + 1] = res[i][j];
				if (p.charAt(j) == s.charAt(i))
					res[i + 1][j + 1] = res[i][j];
				if (p.charAt(j) == '*') {
					if (s.charAt(i) != p.charAt(j - 1) && p.charAt(j - 1) != '.')
						res[i + 1][j + 1] = res[i + 1][j - 1];
					else {
						//res[i + 1][j - 1] 表示*一个都不匹配;
						//res[i + 1][j]表示匹配一个 
						//res[i][j + 1]表示匹配多个
						res[i + 1][j + 1] = res[i + 1][j - 1] || res[i + 1][j] || res[i][j + 1];
					}
				}
			}
		}
		return res[m][n];
	}
}

发表于 2017-07-07 10:09:45 回复(5)

C/C++

Cass998

/*递归清晰版*/
class Solution {
public://以p为主对象分情况讨论
    bool isMatch(const char *s, const char *p) {
        //int n1 = strlen(s), n2 = strlen(p);
        if(*p == '\0') return *s == '\0';
        if(strlen(p) == 1)return (strlen(s) == 1 && (s[0] == p[0] || p[0] == '.'));
        if(p[1] != '*'){
            if(*s == '\0') return 0;
            return (s[0] == p[0] || p[0] == '.') && isMatch(s + 1, p + 1);
        }
        //以下是 p[1] == '*'的情况
        while(*s != '\0' && (s[0] == p[0] || p[0] == '.')){//首元素匹配的情况
            if(isMatch(s, p + 2)) return 1;//先删去p的前两个元素检验（情况1）
            s = s + 1; //删去s首元素检验（情况2）
        }
        //首元素不匹配 和 s为空字符串 的情况 （此时s的首元素可能是后面的）
        return isMatch(s, p + 2);
    }
};

/*递归简化版*/
class Solution {
public:
    bool isMatch(const char *s, const char *p) {//由于p只有一个元素的话，不可能是"*"，所以递归可以简化
        if(*p == '\0') return *s == '\0';
        if(strlen(p) > 1 && p[1] == '*')//无论s首元素是否匹配，先把p的前两个元素去掉;之后去掉匹配的s首元素；即是s首元素去掉与否的讨论
            return isMatch(s, p + 2) || (*s != '\0' && (s[0] == p[0] || p[0] == '.') && isMatch(s + 1, p));
        else return *s != '\0' && (s[0] == p[0] || p[0] == '.') && isMatch(s + 1, p + 1);
    }
};
/* DP版 */
class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        int m = strlen(s), n = strlen(p);
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, 0));
        dp[0][0] = 1;
        for(int i = 0; i <= m; i++)
            for(int j = 1; j <= n; j++){
                if(j > 1 && p[j - 1] == '*')
                    dp[i][j] = dp[i][j - 2] || (i > 0 && (s[i - 1] == p[j - 2] || p[j - 2] == '.') && dp[i - 1][j]);
                else dp[i][j] = i > 0 && dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
            }
        return dp[m][n];
    }
};



/*
递归回溯时是从后往前收，DP是从前往后推。
本质一样，只是推时符号不同；
递归往后调递归函数时是加号，DP往后递推时减号
*/

编辑于 2019-02-03 12:34:22 回复(0)

探花一笑若奈何

 /*
    动态规划
    如果 p[j] == str[i] || pattern[j] == '.', 此时dp[i][j] = dp[i-1][j-1];
    如果 p[j] == '*'
    分两种情况:
    1: 如果p[j-1] != str[i] && p[j-1] != '.', 此时dp[i][j] = dp[i][j-2] //*前面字符匹配0次
    2: 如果p[j-1] == str[i] || p[j-1] == '.'
        此时dp[i][j] = dp[i][j-2] // *前面字符匹配0次
        或者 dp[i][j] = dp[i][j-1] // *前面字符匹配1次
        或者 dp[i][j] = dp[i-1][j] // *前面字符匹配多次
     */
public class Solution {
    public boolean isMatch(String s, String p) {
        int len1 = s.length(),len2 = p.length();
        boolean[][] dp = new boolean[len1+1][len2+1];
        dp[0][0] = true;
        for(int i = 1;i <= len2;i++) 
            if(p.charAt(i-1) == '*')
                dp[0][i] = dp[0][i-2]; 
        for(int i = 1;i <= len1;i++){
            for(int j = 1;j <= len2;j++){
                if(p.charAt(j-1) == '.' || s.charAt(i-1) == p.charAt(j-1)) dp[i][j] = dp[i-1][j-1];
                else if(p.charAt(j-1) == '*'){
                    if(j != 1 && (p.charAt(j-2) != '.' && s.charAt(i-1) != p.charAt(j-2)))
                        dp[i][j] = dp[i][j-2];
                    else
                        dp[i][j] = dp[i][j-2] || dp[i][j-1] || dp[i-1][j];
                }
            }
        }
        return dp[len1][len2];
    }
}

发表于 2018-03-28 21:01:45 回复(2)

你快乐吗

钻空子了

import java.util.regex.*;
public class Solution {
    public boolean isMatch(String s, String p) {
        boolean isMatch = Pattern.matches(p, s);
        return isMatch;
    }
}

发表于 2020-12-09 17:11:26 回复(1)

专业陪跑

/**
     * You are here! Your runtime beats 0.61 % of java submissions.
     * 回溯。。让我笑一会~~
     */
    public boolean isMatch(String s, String p) {
        return check(s.toCharArray(),0,p.toCharArray(),0);
    }
    public boolean check(char[] s,int i,char[] p,int j){
        if(i==s.length&&j==p.length) return true;
        if(i!=s.length&&j==p.length) return false;
        if(j+1<p.length){//第二个不为空
            if(i<s.length){//
                if(p[j+1]=='*'){
                    if(s[i]==p[j]||(p[j]=='.'&&i<s.length))
                        return check(s,i+1,p,j+2)||check(s,i+1,p,j)||check(s,i,p,j+2);
                    else
                        return check(s,i,p,j+2);
                }
            }
            else{//当i==s.length,j!=p.length 例如考虑s=a,p=ab*
                if(j+1<p.length&&p[j+1]=='*')
                    return check(s,i,p,j+2);
                else return false;
            }
        }
        if(i<s.length&&(s[i]==p[j]||p[j]=='.'))//因为最前面的if是判断j+1是否s.length，最后就判断最后一个字符
            return check(s,i+1,p,j+1);
        else
            return false;
    }

发表于 2018-01-23 00:03:50 回复(0)

C/C++

nbgao

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        int l1 = strlen(s);
        int l2 = strlen(p);
        bool dp[l1+1][l2+1];
        memset(dp,false,sizeof(dp));
        dp[0][0] = true;
        for(int i=1;i<l2&&p[i]=='*';i+=2)
        	dp[0][i+1] = true;
        
        for(int i=0;i<l1;i++)
        {
        	for(int j=0;j<l2;j++)
        	{
        		if(p[j] == '.')
        			dp[i+1][j+1] = dp[i][j];
        		else if(p[j] == '*'){
        			if(p[j-1]!=s[i] && p[j-1]!='.')
        				dp[i+1][j+1] = dp[i+1][j-1];
        			else
        				dp[i+1][j+1] = dp[i+1][j-1] || dp[i+1][j] || dp[i][j+1];			
				}else
					dp[i+1][j+1] = (dp[i][j] && s[i]==p[j]);
			}
		}
		return dp[l1][l2];
    }
};

发表于 2017-09-04 01:42:20 回复(1)

元气の悟空

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        return pan(s,p,0,0);
    }
    bool pan(const char *s,const char *p,int si,int pi)
    {
        if(p[pi]=='\0') return s[si]=='\0'?true:false;
        if(p[pi+1]!='*')
            return s[si]!='\0'&&(p[pi]==s[si]||p[pi]=='.')&&pan(s,p,si+1,pi+1);
        for(;s[si]!='\0'&&(s[si]==p[pi]||p[pi]=='.');si++)
            if(pan(s,p,si,pi+2)) return true;
        return pan(s,p,si,pi+2);
    }
};

发表于 2016-08-19 22:27:17 回复(1)

Kanarien

/**
* 正则字符串匹配
* "."匹配任一字符，"*"表示之前那个字符可以有0个，1个或是多个
*
* 思路一：分类递归
* 最直观的做法就是根据s和p的情况进行分类匹配，
* 然后递归判断，每次递归视情况匹配p的前1或2个字符。
* 为使分类清晰，这里根据p字符串的长度进行分类
* 1.当p.length = 0，返回s.isEmpty()
* 2.当p.length = 1(说明没有*)，判断s时候也是长度为1且当前字符能够匹配
* 3.当p.length > 1，且p[1] != "*"(不含"*"的情况)
*   若s为空，返回false，否则就是单一字符进行匹配,递归判断s和p的下一个字符
* 4.当p.length > 1，且p[1] = "*"(含"*"的情况)，
*   则应该把可能重复的s字符逐一匹配然后去掉，使用一个循环，
*   由于"*"的特性，要考虑到当前p的前两个字符可能匹配不到任何的s，
*   所以要先判断下isMatch(s, p.substring(2))
*   即当前p的前两个字符不进行任何匹配。
*   然后再是逐一判断s[0]与p[0]是否相等，是则s取下一字符，否则结束循环。
*   循环结束后，说明p的前两个字符已经匹配完毕，p取后面的字符
*
* 思路二：动态规划
* 关键是状态转移方程
* p.charAt(j) == s.charAt(i) : dp[i][j] = dp[i-1][j-1]
* If p.charAt(j) == ‘.’ : dp[i][j] = dp[i-1][j-1];
*
* If p.charAt(j) == ‘*’: 
* here are two sub conditions: 
*   if p.charAt(j-1) != s.charAt(i) : dp[i][j] = dp[i][j-2] //in this case, a* only counts as empty
*   if p.charAt(i-1) == s.charAt(i) or p.charAt(i-1) == ‘.’: 
*       dp[i][j] = dp[i-1][j] // in this case, a* counts as multiple a 
*       dp[i][j] = dp[i][j-1] // in this case, a* counts as single a 
*       dp[i][j] = dp[i][j-2] // in this case, a* counts as empty
* 示例
* s\p ""  a  *  b  * 
* ""   1  0  1  0  1
*  a   0  1  1  0  1
*  a   0  0  1  0  1
*  a   0  0  1  0  1
*  a   0  0  1  0  1
**/
public class Solution {
    public boolean isMatch(String s, String p) {
        //return isMatch_recursion(s, p);
        return isMatch_dp(s, p);
    }
    
    private static boolean isMatch_recursion(String s, String p) {
        if (p.isEmpty()) {
            return s.isEmpty();
        } else if (p.length() == 1) {
            return s.length() == 1 && (p.equals(s) || p.equals("."));
        } else if (p.charAt(1) != '*') {
            if (s.isEmpty()) {
                return false;
            }
            return (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.')
                && isMatch_recursion(s.substring(1, s.length()), p.substring(1, p.length()));
        } else {
            while (!s.isEmpty() && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.')) {
                if (isMatch_recursion(s, p.substring(2, p.length()))) {
                    return true;
                }
                s = s.substring(1, s.length());
            }
        }
        return isMatch_recursion(s, p.substring(2, p.length()));
    }
    
    private static boolean isMatch_dp(String s, String p) {
        if (s == null || p == null) {
            return false;
        }
        int m = s.length(), n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int i = 1; i < n; i++) { // 初始化第一行，p匹配s = ""
            if (p.charAt(i) == '*' && dp[0][i - 1]) {
                dp[0][i + 1] = true;
            }
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // p[j - 1]不是"*"的情况，单字符匹配
                if (p.charAt(j - 1) == '.' || p.charAt(j - 1) == s.charAt(i - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                // p[j - 1]是"*"的情况，则要判断p[j - 2]是否匹配当前s[i - 1]
                // 若不匹配，则p[j - 1]匹配空字符串
                // 否则，有三种情况：
                //   1.p[j - 1]匹配空字符串；
                //   2.p[j - 1]匹配单一s[i - 1]字符；
                //   3.p[j - 1]匹配多个s[i - 1]字符
                if (p.charAt(j - 1) == '*') {
                    if (p.charAt(j - 2) != s.charAt(i - 1) && p.charAt(j - 2) != '.') {
                        dp[i][j] = dp[i][j - 2];
                    } else {
                        dp[i][j] = dp[i][j - 2] || dp[i][j - 1] || dp[i - 1][j];
                    }
                }
            }
        }
        return dp[m][n];
    }
}

编辑于 2018-11-27 22:03:26 回复(4)

赟儿的colorful_days

为啥 ab .* 是true ab .*c 是false

发表于 2020-08-06 23:49:07 回复(0)

牛客805090309号

isMatch("aab", "c*a*b") → true为啥输出是true?不是要全匹配吗?c没有被匹配

发表于 2020-08-03 15:07:02 回复(2)

小凯凯呢

public class Solution {
    public boolean isMatch(String s, String p) {
        if(s==null||p==null){
            return false;
        }
        return Match(s,0,p,0);
    }
    private boolean Match(String s,int i,String p,int j){
        if(j==p.length()){
            return i==s.length();
        }
        if(j<p.length()-1&&p.charAt(j+1)=='*'){
            if(i!=s.length()&&(s.charAt(i)==p.charAt(j)||p.charAt(j)=='.')){
                return Match(s,i,p,j+2)||Match(s,i+1,p,j);
            }else{
                return Match(s,i,p,j+2);
            }
        }
       if(s.length()!=i&&(s.charAt(i)==p.charAt(j)||p.charAt(j)=='.')){
           return Match(s,i+1,p,j+1);
       }
       return false;
    }
}

发表于 2020-08-03 12:02:04 回复(0)

飘雪的天空201810301449640

public class Solution { public boolean isMatch(String s, String p) { if (p.isEmpty()) { return s.isEmpty(); } else if (p.length() == 1) { return s.length() == 1 && (p.equals(s) || p.equals(".")); } else if (p.charAt(1) != '*') { if (s.isEmpty()) { return false; } return (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.') && isMatch(s.substring(1, s.length()), p.substring(1, p.length())); } else { while (!s.isEmpty() && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.')) { if (isMatch(s, p.substring(2, p.length()))) { return true; } s = s.substring(1, s.length()); } } return false; } }

发表于 2020-07-04 23:16:30 回复(0)

Dancer_Wu

收藏一下大佬的思路
/*   
动态规划  
如果 p[j] == str[i] || pattern[j] == '.', 此时dp[i][j] = dp[i-1][j-1];  
如果 p[j] == '*'   
分两种情况: 
1: 如果p[j-1] != str[i] && p[j-1] != '.', 此时dp[i][j] = dp[i][j-2] //*前面字符匹配0次 
2: 如果p[j-1] == str[i] || p[j-1] == '.' 
   此时dp[i][j] = dp[i][j-2] // *前面字符匹配0次      
   或者 dp[i][j] = dp[i][j-1] // *前面字符匹配1次    
   或者 dp[i][j] = dp[i-1][j] // *前面字符匹配多次     */
public class Solution 
{   
   public boolean isMatch(String s, String p) 
   {       
   int len1 = s.length(),len2 = p.length();     
   boolean[][] dp = new boolean[len1+1][len2+1];   
   dp[0][0] = true;       
   for(int i = 1;i <= len2;i++)        //初始状态，s="";
   if(p.charAt(i-1) == '*')      
   dp[0][i] = dp[0][i-2];     
   for(int i = 1;i <= len1;i++)
   { 
   for(int j = 1;j <= len2;j++)
   {              
   if(p.charAt(j-1) == '.' || s.charAt(i-1) == p.charAt(j-1)) dp[i][j] = dp[i-1][j-1];   
   else if(p.charAt(j-1) == '*')
   {               
   if(j != 1 && (p.charAt(j-2) != '.' && s.charAt(i-1) != p.charAt(j-2)))    
   dp[i][j] = dp[i][j-2];           
   else                 
   dp[i][j] = dp[i][j-2] || dp[i][j-1] || dp[i-1][j];  
   }          
   }    
   }    
   return dp[len1][len2];    
   }
   }

编辑于 2020-04-12 21:40:51 回复(1)

C/C++

(:∇:)我太难了

class Solution {
public:
bool isMatch(const char *s, const char *p) {
int l1 = strlen(s);
int l2 = strlen(p);
bool dp[l1+1][l2+1];
memset(dp,false,sizeof(dp));
dp[0][0] = true;
for(int i=1;i<l2&&p[i]=='*';i+=2)
dp[0][i+1] = true;

for(int i=0;i<l1;i++)
{
for(int j=0;j<l2;j++)
{
if(p[j] == '.')
dp[i+1][j+1] = dp[i][j];
else if(p[j] == '*'){
if(p[j-1]!=s[i] && p[j-1]!='.')
dp[i+1][j+1] = dp[i+1][j-1];
else
dp[i+1][j+1] = dp[i+1][j-1] || dp[i+1][j] || dp[i][j+1];
}else
dp[i+1][j+1] = (dp[i][j] && s[i]==p[j]);
}
}
return dp[l1][l2];
}
};

发表于 2019-08-07 20:09:40 回复(0)

Java

Iosti

public class Solution {
    public boolean isMatch(String s, String p) {
        return s.replaceFirst(p,"Iosti").equals("Iosti");
    }
}

点开一看各位都在用动态规划惊了

编辑于 2019-01-28 19:59:34 回复(2)

TeddyZhang

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        int slen = strlen(s), plen = strlen(p);
        vector< vector<bool> > dp( slen+1, vector<bool>(plen+1, false) ); //增加一行用于特例
        dp[0][0] = true;
        for(int i = 1;i < plen + 1; i++){  //s为空的情况
            if(p[i -1] == '*')
                dp[0][i] = dp[0][i-2];
        }
        for(int i = 1;i < slen + 1; i++){
            for(int j = 1;j < plen + 1; j++){
                if(s[i-1] == p[j-1] || p[j-1] == '.'){
                    dp[i][j] = dp[i-1][j-1];
                }
                else if(p[j-1] == '*'){
                    if(p[j-2] != s[i-1] && p[j-2] != '.'){  // *前字符匹配到0次
                        dp[i][j] = dp[i][j-2];
                    }else{
                        if(p[j-2] == s[i-1] || p[j-2] == '.'){
                            dp[i][j] = dp[i][j-1] || dp[i][j-2] || dp[i-1][j];
                            // *前匹配到0次、1次、多次
                        }
                    }
                }
            }
        }
        return dp[slen][plen];
    }
};

发表于 2018-09-19 13:28:12 回复(0)

胡民阳

//动态规划求解 dp[i][j]代表s{0...i-1}和p{0...j-1}完全匹配
class Solution {
public:
    bool isMatch(string s, string p) {
        int len1 = s.length(), len2 = p.length();
        if (len1 == 0 && len2 == 0)
            return true;
        if (len2 == 0)
            return false;
        int dp[len1 + 1][len2 + 1];
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1; //初始为1
        for (int i = 1; i <= len2; i++)
            if (p[i - 1] == '*')
            dp[0][i] = dp[0][i - 1] || dp[0][i - 2];
            //dp[0][j-1]代表*匹配p中的上一个字符，
            //dp[0][j-2]代表*和上一个字符匹配空

        for (int i = 1; i <= len1; i++){
            for (int j = 1; j <= len2; j++){
                if (s[i - 1] == p[j - 1] || p[j - 1] == '.')
                    dp[i][j] = dp[i - 1][j - 1];
                    //如果s[i-1]和p[j-1]直接匹配，
                    //或者p[j-1]='.'，那么dp[i][j] = dp[i-1][j-1]
                else if (p[j - 1] == '*'){
//如果p[j-1] = '*'，那么X*(X代表任意一个字符）中的*只能匹配X，
                //或者X*直接匹配空
//dp[i][j-2]代表X*匹配空，dp[i-1][j]代表
                //*匹配一个字符（当且仅当p[j-2] == s[i-1]或者p[j-2] = '.')。
                dp[i][j] = dp[i][j-2] || (dp[i-1][j] && (p[j - 2] == s[i - 1] || p[j - 2] == '.'));
                }
            }
        }
        return dp[len1][len2];
    }
};

发表于 2018-09-04 20:31:33 回复(0)

Jerryyyyy

    bool isMatch(string s, string p) {
        int m=s.size(),n=p.size();
        vector<vector<bool>>dp(m+1,vector<bool>(n+1,0));
        dp[0][0]=true;
        for(int i=1;i<=n;i++)
            if(p[i-1]=='*')
                dp[0][i]=dp[0][i-2] || dp[0][i-1];
        for(int i=1;i<=m;i++)
            for(int j=1;j<=n;j++){
                if(p[j-1]=='.' || s[i-1]==p[j-1])
                    dp[i][j]=dp[i-1][j-1];
                if(p[j-1]=='*'){
                    if(p[j-2]!=s[i-1] && p[j-2]!='.')
                        dp[i][j]=dp[i][j-2];
                    else
                        dp[i][j]=dp[i][j-1] || dp[i-1][j] || dp[i][j-2];
                }
            }
        return dp[m][n];
    }

发表于 2018-08-08 13:30:34 回复(0)

小白debug

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        int len1 = strlen(s);
        int len2 = strlen(p);
        if(p == NULL)return false; 
        vector<vector<bool>> DP(len1 + 1, vector<bool>(len2 + 1, false));
        DP[0][0] = true;
        for(int j = 1; j <= len2; j++)
        {
            if(p[j - 1] == '*' && (j - 2 >= 0 && DP[0][j - 2] || DP[0][j - 1]))
                DP[0][j] = 1;            
        }
        for (int i=1; i <= len1; ++i) {
            DP[i][0] = false;
           }
        for(int i = 1; i <= len1; ++i)
        {
            for(int j = 1; j <= len2; ++j)
            {
                if(s[i - 1] == p[j - 1] || p[j - 1] == '.')
                    DP[i][j] = DP[i - 1][j - 1];
                
                else if(p[j - 1] == '*')
                {
                    DP[i][j] = (j - 2 >= 0 && DP[i][j - 2]) || DP[i][j - 1] || 
                    (DP[i - 1][j] && ((i >= 2 && j >= 2 && s[i - 1] == s[i - 2] && s[i - 2] == p[j - 2]) || (j >= 2 && p[j - 2] == '.')));
                    
                }
                else 
                    DP[i][j] = false;   
            }
        }
        return DP[len1][len2];
    }
};

发表于 2018-02-28 15:36:21 回复(0)

牛牛王

测试用例:
"ab",".*" ---->说的很清楚点号匹配任意一个字符，星号匹配前一个元素的一个或者多个
对应输出应该为:
true

发表于 2018-01-23 22:41:34 回复(0)

正则表达式匹配

问题信息

热门推荐

通过挑战的用户

相关试题