Wildcard Matching

来源：Leetcode

原帖：https://oj.leetcode.com/problems/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") ? 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

代码：

 class Solution {  
 public:  
   // s does NOT include '?' and '*'. p has '?' and '*'  
   //Version 1: iteration  
   bool isMatch(const char *s, const char *p) {  
     const char *start_s = NULL, *start_p = NULL;  
     while (*s != '\0') {  
       if (*p == '?' || *s == *p) {  
         s++;  
         p++;  
       } else if (*p == '*') {  
         while (*p == '*') p++;  
         if (*p == '\0') return true;  
         start_s = s;  
         start_p = p;  
       } else {  
         if (!start_s) return false;  
         s = ++start_s;  
         p = start_p;  
       }  
     }  
     while (*p == '*') p++;  
     return *s == '\0' && *p == '\0';  
   }  
 };  
   
 class Solution {  
 public:  
   //Version 2: recursion:   
   // time limit exceed  
   bool isMatch(const char* s, const char* p) {  
     if (*s == '\0') {  
       while(*p && *p == '*') p++;  
       return *p == '\0';  
     }  
     if (*s == *p || *p == '?') {  
       return isMatch(s+1, p+1);  
     } else if (*p == '*') {  
       while (*p == '*') p++;  
       if (*p == '\0') return true;  
       while (*s != '\0') {  
         if (isMatch(s, p)) return true;  
         s++;  
       }  
     }  
     return false;  
   }  
 };