## 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

[解题思路]

[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:    }
``````