LeetCode [44] Wildcard Matching

 44. Wildcard Matching

Hard

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*' where:

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

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

 

Example 1:

Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input: s = "aa", p = "*"
Output: true
Explanation: '*' matches any sequence.

Example 3:

Input: s = "cb", p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.

Example 4:

Input: s = "adceb", p = "*a*b"
Output: true
Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".

Example 5:

Input: s = "acdcb", p = "a*c?b"
Output: false

 

Constraints:

• 0 <= s.length, p.length <= 2000
• s contains only lowercase English letters.
• p contains only lowercase English letters, '?' or '*'.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94

//c++: dp 1580ms class Solution { public: bool isMatch(string s, string p) { int m = s.size(), n = p.size(); vector<vector<bool>> dp(m+1, vector<bool>(n+1, false)); dp[0][0] = true; for(int j=1; j<=n; ++j){ if(p[j-1]=='*') dp[0][j] = true; else break; } for(int i=1; i<=m; ++i){ for(int j=1; j<=n; ++j){ if(p[j-1]!='*'){ dp[i][j] = dp[i-1][j-1]&&(s[i-1]==p[j-1]||p[j-1]=='?'); }else{ dp[i][j] = dp[i-1][j]||dp[i][j-1]; } } } return dp[m][n]; } }; //C: Method1 TLE!!! class Solution { public: bool isMatch(const char *s, const char *p) { if(*p=='\0') return (*s=='\0'); if(*s=='\0') return (*p=='\0'); if(*p=='*'){ bool ended = false; for(int i=0; !ended; ++i){ if(*(s+i)=='\0') ended = true; if (isMatch(s+i, p+1)) return true; } }else{ if(*p==*s || *p=='?'){ return isMatch(s+1, p+1); }else return false; } return false; } }; //C: Method2 10ms bool isMatch(char* s, char* p) { char *star = NULL; char *ms = NULL; while(*s){ if(*p==*s||*p=='?'){ s++; p++; }else if(*p=='*'){//forget the earlier stars, only the latest matters star = p++; ms = s;//'*' matches zero char }else if(star){//found a dismatch s = ++ms;//'*' matches one more char p = star+1;//backtracking }else//mismatch and no effective '*' return false; } while (*p=='*') p++; return *p=='\0'; } //C++: Method2 31ms class Solution { public: bool isMatch(string s, string p) { int i=0, j=0; int ns = s.size(); int np = p.size(); int star = -1;//position of the last star int ms;//position of the last matched s while(i<ns && (j<np||star>=0)){ if(s[i]==p[j]||p[j]=='?'){ i++; j++; }else if(p[j]=='*'){ star = j++; ms = i-1;//the '*' matches zero characters of s }else if(star>=0){ i = ++ms;//the '*' positioned at star matches one more character of s j = star+1; }else{ return false; } } if(i<ns) return false; while(j<np && p[j]=='*') j++; return j==np; } };