44. 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:

DFS + DP.

Lets assume i, j are index for s and p.

1. if p[j] == '*', 3 direction we can go:
   1. dfs(i+1, j) --> meaning * represent more than 1 chars
   2. dfs(i+1, j+1) --> meaning * represent 1 char
   3. dfs(i, j+1) --> meaning * represent empty, we skip it.
2. p[j] != '*', it has to be s[i] == p[j] OR s[i] == '?', and we are moving on with dfs(i+1, j+1). Or we should return false;

Base case:

1. when i == s.length, meaning no more char to compare from s.
   1. we scan through rest of p[starting from j] and make sure its all "*" left, otherwise return false
2. when j==p.length (and i < s.length), this is a FALSE for sure.

We need to create a DP[][] to keep track of what are the i, j combination that returned FALSE already to speed up the calculation.

Complexity:

Time:

Space:

Code:

public class Solution {

    private int[][] visited = null;
    public boolean isMatch(String s, String p) {
        if(s==null || p ==null){
            return false;
        }

        if(s.length() == 0){
            for(int i = 0; i < p.length(); i++){
                if(p.charAt(i) != '*'){
                    return false;
                }
            }
            return true;
        }
        char[] ss = s.toCharArray();
        char[] pp = p.toCharArray();
        visited = new int[ss.length+1][pp.length+1];
        return dfs(ss, pp, 0, 0);
    }

    private boolean dfs(char[] ss, char[] pp, int i, int j){

        if(visited[i][j] == 1){
            return false;
        }

        if(i == ss.length){
            for(int index = j; index < pp.length; index++){
                if(pp[index] != '*'){
                    visited[i][j]=1;
                    return false;
                }
            }
            return true;
        }

        if(j == pp.length){
            visited[i][j]=1;
            return false;
        }

        if(pp[j] == '*'){

            if(dfs(ss, pp, i+1, j+1) || dfs(ss, pp, i+1, j) || dfs(ss, pp, i, j+1))
            {
                return true;
            }

            visited[i][j] = 1;
            return false;
        }
        if((ss[i]==pp[j] || pp[j]=='?') && dfs(ss, pp, i+1, j+1)){
            return true;
        }
        visited[i][j] = 1;
        return false;
    }
}