[LeetCode]Regular Expression Matching、Wildcard Matching

121 阅读 0 评论 80 点赞

我是靠谱客的博主阳光面包，最近开发中收集的这篇文章主要介绍[LeetCode]Regular Expression Matching、Wildcard Matching，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Regular Expression Matching：

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") ? false
isMatch("aa","aa") ? true
isMatch("aaa","aa") ? false
isMatch("aa", "a*") ? true
isMatch("aa", ".*") ? true
isMatch("ab", ".*") ? true
isMatch("aab", "c*a*b") ? true

DP的思想跃然纸上啊，注意分情况讨论即可。

注意下面代码中当 p[j-1] == '*' 的时候的判断比较烦，有几种情况是为true的，最后那个括号里的判断没有的话是不能AC的，为了解决的情况是比如

aa 要和a*匹配，括号里的意思是既然另一个子串是*，那么判断再多一个*前的那个字符能不能把我也匹配了。

LeetCode的用例还是比较简单，没有两个子串都有*的情况。

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function    
        
        if ( !s || !p )
		    return !s&&!p;
	    int ns=strlen(s);
	    int np=strlen(p);
	    vector<vector<bool> > dp(ns+1,vector<bool>(np+1,0));
	    dp[0][0]=true;
	    for(int i=1;i<=ns;i++)
	    {
		    if ( s[i-1]=='*' )
		    {
			    assert(i>=2);
			    dp[i][0]=dp[i-2][0];
		    }
	    }
	    for(int j=1;j<=np;j++)
	    {
		    if ( p[j-1]=='*' )
		    {
			    assert(j>=2);
			    dp[0][j]=dp[0][j-2];
		    }
	    }
	    for(int i=1;i<=ns;i++)
	    {
		    for(int j=1;j<=np;j++)
		    {
			    if (s[i-1]=='.'||p[j-1]=='.')
				    dp[i][j]=dp[i-1][j-1];
			    else if ( s[i-1]=='*')
				    dp[i][j]=dp[i-1][j]||dp[i-2][j];
			    else if ( p[j-1]=='*')
				    dp[i][j]=dp[i][j-1]||dp[i][j-2]||(dp[i-1][j]&&(s[i-1]==p[j-2]||p[j-2]=='.'));
			    else
				    dp[i][j]=dp[i-1][j-1]&&s[i-1]==p[j-1];
		    }
	    }
	    return dp[ns][np];
    }

};

Wildcard Matching：

Implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") ? false
isMatch("aa","aa") ? true
isMatch("aaa","aa") ? false
isMatch("aa", "*") ? true
isMatch("aa", "a*") ? true
isMatch("ab", "?*") ? true
isMatch("aab", "c*a*b") ? false

思路是一样的，但是这个要比上一个简单一点。还是注意当 p[j]=='*'的时候。

但是大数据的时候，这回O(n2)的这个算法居然不给过了~ 空间溢出，不知道怎么设的~那就逼俺们写个递归的呗～

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        if (!s||!p)
		    return !s&&!p;
	    int na=strlen(s);
	    int nb=strlen(p);
	    vector<vector<char> > dp(na+1,vector<char>(nb+1,0));
	    dp[0][0]=1;
	    for(int i=1;i<=na;i++)
		    if(s[i-1]=='*')
			    dp[i][0]=dp[i-1][0];
	    for(int j=1;j<=nb;j++)
		    if(p[j-1]=='*')
			    dp[0][j]=dp[0][j-1];
	    for(int i=1;i<=na;i++)
	    {
		    for(int j=1;j<=nb;j++)
		    {
			    if (s[i-1]=='?'||p[j-1]=='?')
				    dp[i][j]=dp[i-1][j-1];
			    else if(s[i-1]=='*')
				    dp[i][j]=(dp[i-1][j]||dp[i-1][j-1])?1:0;
			    else if (p[j-1]=='*')
				    dp[i][j]=(dp[i][j-1]||dp[i-1][j-1]||dp[i-1][j])?1:0;
			    else
				    dp[i][j]=(dp[i-1][j-1]&&s[i-1]==p[j-1])?1:0;
		    }
	    }
	    return dp[na][nb];
    }
};

递归方法如下，小数据给过，大数据妥妥TLE。。。

class Solution {
public:
    bool isMatch(const char *ss, const char *sp) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
	    if (!s || !p )
		    return !s&&!p;
	    else if ( *s=='' || *p=='' )
	    {
		    const char* end=*s==''?s:p;
		    const char* oth=end==s?p:s;
		    int i=0;
		    for(;oth[i]!='';i++)
			    if (oth[i]!='*')
				    break;
		    return oth[i]=='';
	    }
	    else if ( *s=='?' || *p=='?' )
		    return isMatch(s+1,p+1);
	    else if ( *s=='*' || *p=='*' )
	    {
		    const char* star=*s=='*'?s:p;
		    const char* oth=star==s?p:s;
		    while(*star=='*'&&*star!='')
			    star++;
		    int i=0;
		    for(;oth[i]!='';i++)
			    if (isMatch(star,oth+i))
				    return true;
		    return isMatch(star,oth+i);
	    }
	    else
		    return *s==*p&&isMatch(s+1,p+1);
    }
};

递归TLE了之后呢，我又倒回来想DP怎么再优化一下，后来发现Leetcode讨论区有这个题的讨论，发现人家的空间优化过后是O(n)的，原来是考虑到dp记录数组的更新是一行一行来的，每次最多用到上一行，所以当然可以只用两行来滚动更新好了，大赞！！！！！！以前都没有想到过可以这样优化空间啊~ 一直以来做题想的都是时间复杂度，空间复杂度很少去考虑的。回来把空间优化了，然后又发现多个连续的*****其实跟一个*是一样的，所以对原字符串预处理一下，加了这个代码，结果现在变成了超时。。。

怎么想都想不通，优化后空间是O(n)，时间最坏也是O(n*m)啊，跟讨论区里不一样的吗？怎么会不过。。。

看了下超时的那个例子，原来是如果 s长度大于p的长度，要把这里剪枝了。。。反过来又讲一下，LeetCode里没有考虑两个子串都有*的情况。把这个剪枝加上之后，终于AC了~ 呼~~~~~~ 蛮有收获的~

看来空间的优化一定要记住！！！

class Solution {
public:
    bool isMatch(const char *ss, const char *sp) {
		// Start typing your C/C++ solution below
		// DO NOT write int main() function

		if ( !ss||!sp )
			return !ss&&!sp;
		string s=simplify(ss);
		string p=simplify(sp);
		int na=s.length();  
		int nb=p.length();  
		if ( na <nb )
		{
			int notStar=nb-count(p.begin(),p.end(),'*');
			if (na < notStar )
				return false;
		}
		vector<vector<bool> > dp(2,vector<bool>(nb+1,false));  
		dp[0][0]=1;  
		for(int j=1;j<=nb;j++)  
			if(p[j-1]=='*')  
				dp[0][j]=dp[0][j-1];  
		for(int i=1;i<=na;i++)  
		{  
			int curRow=i%2;
			int preRow=(i+1)%2;
			dp[curRow][0]=dp[preRow][0]&&s[i-1]=='*';
			for(int j=1;j<=nb;j++)  
			{	  
				if (s[i-1]=='?'||p[j-1]=='?')  
					dp[curRow][j]=dp[preRow][j-1];  
				else if(s[i-1]=='*')  
					dp[curRow][j]=(dp[preRow][j]||dp[preRow][j-1]); 
				else if (p[j-1]=='*')  
					dp[curRow][j]=(dp[curRow][j-1]||dp[preRow][j-1]||dp[preRow][j]);  
				else  
					dp[curRow][j]=(dp[preRow][j-1]&&s[i-1]==p[j-1]);  
			}
		}  
		return dp[na%2][nb];  
	}
	string simplify(const char *s)
	{
		vector<char> oneStar;
		char pre='#';
		while(*s!='')
		{
			if ( !(pre=='*'&&*s==pre))
			{
				oneStar.push_back(*s);
				pre=*s;
			}
			s++;
		}
		return string(oneStar.begin(),oneStar.end());
	}
};

最后贴一个讨论区里贪心写的算法，80ms过大数据。。。虽然我不知道为什么贪心是对的。。。

这个世界神人真是多啊。。。

class Solution {
public:
bool isMatch(const char *s, const char *p) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    if(!s && !p) return true;

    const char *star_p=NULL,*star_s=NULL;

    while(*s)
    {
        if(*p == '?' || *p == *s)
        {
            ++p,++s;
        }else if(*p == '*')
        {
            //skip all continuous '*'
            while(*p == '*') ++p;

            if(!*p) return true; //if end with '*', its match.

            star_p = p; //store '*' pos for string and pattern
            star_s = s;
        }else if((!*p || *p != *s)  && star_p)
        {
            s = ++star_s; //skip non-match char of string, regard it matched in '*'
            p = star_p; //pattern backtrace to later char of '*'
        }else
            return false;
    }

    //check if later part of p are all '*'
    while(*p)
        if(*p++ != '*')
            return false;

    return true;
}
};