Leetcode:44. Wildcard Matching

Description

Implement wildcard pattern matching with support for '?' and '*'.

Example

'?' 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

思路

• 思路一：遞歸，TLE
• 思路二：迭代回溯，兩個指針
  • is：指向s的下一次迭代的位置，初始為同p的'*'對應位置，然後以後的每一次迭代加1
  • ip: 指向p的最近的一個'*'的位置

代碼

• 遞歸超時。

  bool isMatch(string s, string p) {
      int slen = s.size(), plen = p.size();
      string pattern;
      int j = 0;
      while (j < plen){
          if (j > 0 && p[j] == '*' && p[j - 1] == p[j]){
              j++;
              continue;
          }
          pattern += p[j++];
      }
      return helper(s, slen, 0, pattern, pattern.size(), 0);
  }
  
  bool helper(string &s, int slen, int i, string &p, int plen, int j){
      if (i == slen && j == plen) return true;
      if (j == plen) return false;
      if (i == slen) return p[j] == '*' ? helper(s, slen, i, p, plen, j + 1) : false;
  
      if (s[i] == p[j] || p[j] == '?')
          return helper(s, slen, i + 1, p, plen, j + 1);
      else if (p[j] == '*'){
          bool flag = false;
          while (j + 1 < plen && p[j + 1] == p[j]) j++;
  
          flag = helper(s, slen, i + 1, p, plen, j);
          if (!flag && j + 1 < plen && (p[j + 1] == s[i] || p[j + 1] == '?'))
              flag = helper(s, slen, i, p, plen, j + 1);
  
          return flag;
      }
  
      else return false;
  }

• 迭代回溯

  class Solution {
  public:
     bool isMatch(string s, string p) {
      int slen = s.size(), plen = p.size();
  
      int i = 0, j = 0, is = -1, ip = -1;
      while(i < slen){
          if(p[j] == '*'){
              is = i;
              ip = j++;
          }
          else{
              if(s[i] == p[j] || p[j] == '?'){
                  i++;
                  j++;
              }
              else if(ip == -1) return false;
              else {
                  i = ++is;
                  j = ip + 1;
              }
          }
      }
  
      while(j < plen && p[j] == '*') j++;
      return j == plen;
  }
  };