Wildcard Matching

isMatch.java

/*
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

Algorithm:
1. It will be easy to complete in a recusive function but it will not pass the large data set.
2. Details on the algorithm in the comment below
*/
public class Solution {
    public boolean isMatch(String s, String p) {
        // Start typing your Java solution below
        // DO NOT write main() function
        return isMatchHelper(s,p,0,0);
    }
    public boolean isMatchHelper(String s, String p,int ss, int ps) {
        // show all the conditions that will generate the result
        if(ss == s.length() && ps == p.length()) return true;
        if(ss == s.length() && ps < p.length()) {
            while(ps < p.length() && p.charAt(ps) == '*') ps++;
            if(ps == p.length()) return true;
            else return false;
        }
        if(ps == p.length() && ss < s.length()) {
            if(ps > 0 && p.charAt(ps-1) == '*') return true;
            else return false;
        }
        
        // recusively run the function if it does not return true
        // 3 kinds of condition
        // 1. if s and p has the same char
        if(p.charAt(ps) != '*' && (s.charAt(ss) == p.charAt(ps) || p.charAt(ps) == '?')) {
            if(isMatchHelper(s,p,ss+1,ps+1)) return true;
        }
        
        if(p.charAt(ps) == '*') {
            // 2. if the p has * at ps, and try skip it first
            if(isMatchHelper(s,p,ss,ps+1)) return true;
            for(int i = ss+1 ; i < s.length(); i++) {
                // 3. try skip more chars on s.
                if(isMatchHelper(s,p,i,ps)) return true;
            }
        }
        return false;
    }
}