Problem:

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

Reference: http://shmilyaw-hotmail-com.iteye.com/blog/2154716

Method 1:  Greedy

str: the original string we need to examine

pattern: the string with wildcard

s: the cursor in str

p: the cursor in p

StarIdx: the place of the last encountered * (Initialize as -1)

match: the place in str, when p encountered a *

  • We go through every char in str
    • If p and s match, p++, s++
    • If p and s do not match, and p encounter a *: remember the current place of p and s in ‘StarIdx’ and ‘match’. Then, p++l .
    • If p and s do not match, and p does not encounter a *, but StarIdx is not  -1: update p as StarIdx+1, update match as match+1, update s as match.
    • If p and s do not match, and p does not currently at a *, and p does not ever encountered an * before, we can decide, the two string do not match. Return false;
  • After checking every char in str, we need to check if there are still char left in p. We only allow *.

Code:

public class Solution {
    public boolean isMatch(String str, String pattern) {
        int s = 0; // cursor for traversal in str.
        int p = 0; // cursor for traversal in pattern.
        int starIdx = -1; // once we found a star, we want to record the place of the star.
        int match = 0; // once we found a star, we want to start to match the rest of pattern with str, starting from match; this is for remembering the place where we need to start.
        
        // we check and match every char for str.
        while (s < str.length()){
            // 1. case 1: we are not currently at any *, 
            if (p < pattern.length() && (pattern.charAt(p) == str.charAt(s) || pattern.charAt(p) == '?')){
                p++;
                s++;
            }// 2. case 2: we are currently at a '*'
            else if (p < pattern.length() && pattern.charAt(p) == '*' ){
                starIdx = p;
                p++;
                match = s;
            } // 3. case 3: they do not match, we do not currently at a *, but the last matched is a *
            else if (starIdx != -1){
                match++;
                s = match;
                p = starIdx + 1;
            } // 4. case 4: they do not match, do not currently at a *, and last matched is not a *, then the answer is false;
            else{
                return false;
            }
        }
        // when we finish matching all characters in str, is pattern also finished? we could only allow '*' at the rest of pattern
        while (p < pattern.length() && pattern.charAt(p) == '*')
        p++;
  
        return p == pattern.length();
    }
}

Method 2:

We could use recursive method. Recursive: we just check one step. Iterative: we use while to check all steps.

  • Parameters:
    • String str: the original string
    • String pattern: the pattern string
    • int l: the cursor in original string
    • int r: the cursor in pattern string
  • Function: starting from l and r, the left part do match.
  • Base Case: If r reaches the end of str, we need to check if l also reaches the end of pattern. If so, match.
  • Reduction: check the current char in pattern string
    • If regular, just increase l and r by 1;
    • If *, first, go to the last *, and then check if match. (we have to use while loop to find the correct starting point.)

Code for method 2:

public class Solution {
    public boolean isMatch(String s, String p) {
        return helper(s,p,0,0);
        
    }
    
    
    boolean helper(String s, String p, int l, int r) {
           if(r == p.length()) return l == s.length();
           
           if(p.charAt(r) == '*') {
                 while(r < p.length() && p.charAt(r) == '*') r++;   // Move the index at p to a non-start char.
                 while(l < s.length()) {
                     if(helper(s, p, l, r)) return true; // Find one match, return true.
                      l++; // Try the next one.
                  }
                 return helper(s, p, l, r);
            }else if(l < s.length() && (p.charAt(r) == '?' || s.charAt(l) == p.charAt(r))){
                return helper(s, p, l + 1, r + 1);
            }else{
                 return false;
            }
    }

}

Method 3:

However, the recursive method is too slow and we need to have a quicker speed. So we try to solve it by DP.

1. Regular case: if two chars are the same, or p is ‘?’, then go to check dp[i-1][j-1]

2. Special case: when p is ‘*’, we need to check dp[i-1][j-1] for every i>0. If there is one true, then the answer is true.

Code for method 3:

// use DP
public class Solution {
    public boolean isMatch(String s, String p) {
        int width = s.length();
        int height = p.length();
        
        boolean[][] dp = new boolean[width + 1][height + 1];
        dp[0][0] = true;
        
        for (int i = 1; i <= width; i++){
            for (int j = 1; j <= height; j++){
                if (s.charAt(i-1) == p.charAt(j-1) || p.charAt(j-1) == '?'){
                    dp[i][j] = dp[i-1][j-1];
                }else if (p.charAt(j-1) == '*'){
                    int cur = i;
                    while (cur > 0){
                        if (dp[cur-1][j-1]){
                            dp[i][j]= true;
                            break;
                        }
                        cur--;
                    }
                }
            }
        }
        
        return dp[width][height];
    }
}