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).

Example

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

Notes:

1. Double Sequence DP
2. State: f[i][j] can match s[0..i-1] and p[0..j]
3. Function: when s[i-1] match p[j-1], f[i][j] = f[i-1][j-1] || (p[j-1] == '*' && (f[i-1][j] || f[i][j-1])). f[i-1][j] represents '*' could be more than 1. f[i][j-1] represents '*' could be 0.
4. Initialize: f[0][0] = true, f[i][j] = f[i][j-1] && p[j-1] == '*'
5. Answer: f[m][n]

   public boolean isMatch(String s, String p) {
        if (s == null || p == null) {
            return false;
        }

        int m = s.length();
        int n = p.length();

        // state
        boolean[][] f = new boolean[m+1][n+1];

        // initialzie
        f[0][0] = true;
        for (int i = 0; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                f[i][j] = f[i][j-1] && p.charAt(j-1) == '*';
            }
        }

        // function
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (match(s.charAt(i-1), p.charAt(j-1))) {
                    f[i][j] = f[i-1][j-1] || (p.charAt(j-1) == '*' && (f[i-1][j] || f[i][j-1]));
                }
            }
        }

        // answer
        return f[m][n];
    }

    private boolean match(char a, char b) {
        if (b == '*' || b == '?') {
            return true;
        }

        return a == b;
    }