Google+ Followers

Saturday, January 12, 2013

[LeetCode] Wildcard Matching, Solution


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
» Solve this problem

[解题思路]
主要是*的匹配问题。p每遇到一个*,就保留住当前*的坐标和s的坐标,然后s从前往后扫描,如果不成功,则s++,重新扫描。

[Code]
1:    bool isMatch(const char *s, const char *p) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      bool star = false;  
5:      const char *str, *ptr;  
6:      for(str = s, ptr =p; *str!='\0'; str++, ptr++)  
7:      {  
8:        switch(*ptr)  
9:        {  
10:          case '?':  
11:            break;  
12:          case '*':  
13:            star =true;  
14:            s=str, p =ptr;  
15:            while(*p=='*')  
16:              p++;  
17:            if(*p == '\0') // 如果'*'之后,pat是空的,直接返回true  
18:              return true;  
19:            str = s-1;  
20:            ptr = p-1;  
21:            break;  
22:          default:  
23:          {  
24:            if(*str != *ptr)  
25:            {  
26:              // 如果前面没有'*',则匹配不成功  
27:              if(!star)  
28:                return false;  
29:              s++;  
30:              str = s-1;  
31:              ptr = p-1;  
32:            }  
33:          }  
34:        }  
35:      }  
36:      while(*ptr== '*')  
37:        ptr++;  
38:      return (*ptr == '\0');  
39:    }  


Post a Comment