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

Analysis

• 注意这题和regular expression matching的区别：'*' here matches any sequence of chars, not preceding chars

Code

• 1st method: Backtracking: got TLE from leetcode OJ (wrote by myself)

public class Solution {
    public boolean isMatch(String s, String p) {
        if (p.isEmpty()) {return s.isEmpty();}

        if (s.isEmpty()) {
            for (int i=0; i<p.length(); i++) {
                if (p.charAt(i)!='*') return false;
            }
            return true;
        }

        if (p.charAt(0)=='*'){
            while (p.charAt(0)=='*') {
                p = p.substring(1);
                if (p.equals("")) return true;
            }
            for (int i=0; i<=s.length(); i++){
                if (isMatch(s.substring(i), p)) {return true;}
            }
            return false;
        }

        else if (p.charAt(0)!='?' && (s.charAt(0)!=p.charAt(0))) {
            return false;
        }

        return isMatch(s.substring(1), p.substring(1));
    }
}

• 2nd method: Linear run time

int is=0, ip=0, match=0, starIdx = -1;
          while (is < s.length()){
              if (ip<p.length() && (p.charAt(ip)=='?' || s.charAt(is)==p.charAt(ip))) {
                  is++;
                  ip++;
              }
              else if (ip < p.length() && p.charAt(ip)=='*'){
                  starIdx = ip;
                  match = is;
                  ip++;
              }
              else if (starIdx != -1){
                  ip = starIdx+1;
                  match++;
                  is = match;
              }
              else return false;
          }
          while (ip < p.length() && p.charAt(ip) == '*')
                ip++;

         return ip == p.length();

Note

• Code 2 need more understanding!

Reference

Ref for 2nd code:

• Yu
• Leetcode