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") → falseisMatch("aa","aa") → trueisMatch("aaa","aa") → falseisMatch("aa", "*") → trueisMatch("aa", "a*") → trueisMatch("ab", "?*") → trueisMatch("aab", "c*a*b") → false

解题思路：

这道题与http://blog.csdn.net/kangrydotnet/article/details/46624353类似，注意这里的*号与Regular Expression Matching不同。能够採用Regular Expression Matching开发架构，用递归的方法。

可是会出现超时问题：

class Solution {public:    bool isMatch(string s, string p) {        return matchHelper(s, p, 0, 0);    }        bool matchHelper(string& s, string& p, int i, int j){        if(p[j]=='\0'){            return s[i]=='\0';        }        if(p[j]!='*'){            return ((s[i]==p[j] || p[j]=='?'&&s[i]!='\0') && matchHelper(s, p, i+1, j+1));        }                //p[j]=='*'        while(s[i]!='\0'){            if(matchHelper(s, p, i, j+1)) return true;            i++;        }        return matchHelper(s, p, i, j+1);    }};

当输入"aaabbbaabaaaaababaabaaabbabbbbbbbbaabababbabbbaaaaba", "a*******b"时，上述代码超时。原因是有连续的*。于是修正输入，将a******b改成a*b，例如以下：

class Solution {public:    bool isMatch(string s, string p) {		string newP = "";		for (int i = 0; i < p.length(); i++){			if (i>0 && p[i - 1] == p[i] && p[i]=='*'){				continue;			}			newP += p[i];		}		return matchHelper(s, newP, 0, 0);	}	bool matchHelper(string& s, string& p, int i, int j){		if (p[j] == '\0'){			return s[i] == '\0';		}		if (p[j] != '*'){			return ((s[i] == p[j] || p[j] == '?'&&s[i] != '\0') && matchHelper(s, p, i + 1, j + 1));		}		//p[j]=='*'		while (s[i] != '\0'){			if (matchHelper(s, p, i, j + 1)) return true;			i++;		}		return matchHelper(s, p, i, j + 1);	}};

当输入很大的时候。仍然超时：

"abbabaaabbabbaababbabbbbbabbbabbbabaaaaababababbbabababaabbababaabbbbbbaaaabababbbaabbbbaabbbbababababbaabbaababaabbbababababbbbaaabbbbbabaaaabbababbbbaababaabbababbbbbababbbabaaaaaaaabbbbbaabaaababaaaabb", "**aa*****ba*a*bb**aa*ab****a*aaaaaa***a*aaaa**bbabb*b*b**aaaaaaaaa*a********ba*bbb***a*ba*bb*bb**a*b*bb"

经分析。递归调用时，会反复计算。能够用一个二维数组d[i][j]记录s[0...i]与p[0...j]是否匹配。

class Solution {public:	bool isMatch(string s, string p) {		string newP = "";		for (int i = 0; i < p.length(); i++){			if (i>0 && p[i - 1] == p[i] && p[i] == '*'){				continue;			}			newP += p[i];		}		int sLen = s.length();		int pLen = newP.length();				vector
     
      
       > d(sLen + 1, vector
       
        (pLen + 1, true));		return matchHelper(s, newP, 0, 0, d);	}	bool matchHelper(string& s, string& p, int i, int j, vector
        
         
          >& d){		if (p[j] == '\0'){			return (d[i][j] = s[i] == '\0');		}		if (p[j] != '*'){			return (d[i][j] = (s[i] == p[j] || p[j] == '?'&&s[i] != '\0') && d[i + 1][j + 1] && matchHelper(s, p, i + 1, j + 1, d));		}		//p[j]=='*'		while (s[i] != '\0'){			if ((d[i][j] = d[i][j + 1] && matchHelper(s, p, i, j + 1, d))) return true;			i++;		}		return (d[i][j] = d[i][j + 1] && matchHelper(s, p, i, j + 1, d));	}};
         
        
       
      
     

这里运用短路原则。

速度倒是很快。可是会产生内存溢出错误。由于空间复杂度为O(m*n)。

终于办法參考水中的鱼：http://fisherlei.blogspot.com/2013/01/leetcode-wildcard-matching.html，详细仍不是非常明确：

class Solution {public:	bool isMatch(string s, string p) {		bool star = false;		int sStart = 0, pStart = 0;		int str, ptr;		for(str=sStart, ptr = pStart; s[str]!='\0'; str++, ptr++){		    switch(p[ptr]){		        case '?':		            break;		        case '*':		            star = true;		            sStart = str, pStart = ptr;		            while(p[pStart]=='*'){		                pStart++;		            }		            if(p[pStart]=='\0'){		                return true;		            }		            str = sStart - 1;		            ptr = pStart - 1;		            break;		        default:		            if(s[str]!=p[ptr]){		                if(!star){		                    return false;		                }		                sStart++;		                str = sStart-1;		                ptr = pStart-1;		            }		            break;		    }		}		while(p[ptr]=='*')		    ptr++;		return p[ptr]=='\0';	}};