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
此题目和 Regular Expression Matching 非常相像，但有不一样，可以对比分析
方法一，递归，不过超时了 时间复杂度 O(n!*m!)，空间复杂度 O(n)
Submission Result: Time Limit ExceededMore Details
Last executed input: "babaabbbbbaaaaabbaababbaaaaaaabbaabaabbbabbaabbbbb", "*ba**bbbb
class Solution { public: bool isMatch(const char *s, const char *p) { //cout << "==========" << endl; //cout << "s\t" <<s <<endl; //cout << "p\t" <<p <<endl; if(*s == '\0') { if(*p == '\0') return true; while(*p != '\0') { if(*p != '*') return false; p++; } // *p == '\0' now return true; } if(*s == *p || *p == '.') return isMatch(s+1, p+1); else { if(*p == '*') { s++; while(*s != '\0') { if(isMatch(s, p)) return true; else s++; } // *s == '\0' now return isMatch(s, p); } else return false; } } };
方法二：迭代 迭代版，时间复杂度 O(n*m)，空间复杂度 O(1)
copy from https://github.com/haoel/leetcode/blob/master/src/wildcardMatching/wildcardMatching.cpp
bool isMatch(const char *s, const char *p) { const char *last_s = NULL; const char *last_p = NULL; while( *s != '\0' ){ if (*p=='*'){ //skip the "*", and mark a flag p++; //edge case if (*p=='\0') return true; //use last_s and last_p to store where the "*" match starts. last_s = s; last_p = p; }else if (*p=='?' || *s == *p){ s++; p++; }else if (last_s != NULL){
// 如果有*出现，且当前*p和*s不相等，就把p指向原来的*下一个字符，s在原来的last_s 基础上++，同时增加last_s
// check "last_s" to know whether meet "*" before // if meet "*" previously, and the *s != *p // reset the p, using '*' to match this situation p = last_p; s = ++last_s; }else{ // *p is not wildcard char, // doesn't match *s, // there are no '*' wildcard matched before return false; } } //edge case: "s" is done, but "p" still have chars. while (*p == '*') p++; return *p == '\0'; }
sl.isMatch("bacccbbbbb", "*ba**bbbb") 的s和p的输出：
s bacccbbbbb p *ba**bbbb s bacccbbbbb p ba**bbbb s acccbbbbb p a**bbbb s cccbbbbb p **bbbb s cccbbbbb p *bbbb s cccbbbbb p bbbb s ccbbbbb p bbbb s cbbbbb p bbbb s bbbbb p bbbb s bbbb p bbb s bbb p bb s bb p b s b p //不相等，p重新指向last_p，s = ++last_s; 果然是高手啊 s bbbb p bbbb s bbb p bbb s bb p bb s b p b