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

link: https://www.youtube.com/watch?v=3ZDZ-N0EPV0

https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/WildCardMatching.java

Induction rule:

T[i][j] = T[i - 1][j - 1] if s[i] == p[j] || p[j] == '?'

T[i][j] = T[i - 1][j] || T[i][j - 1] if p[j] == '*'

T[i][j] = false otherwise

Solution

public boolean isMatch(String s, String p) {
    boolean[][] m = new boolean[s.length() + 1][p.length() + 1];
    m[0][0] = true;
    for (int i = 0; i < p.length(); ++i) {
        if (p.charAt(i) == '*' && (i == 0 || m[0][i])) {
            m[0][i + 1] = true;
        }
    }
    for (int i = 1; i <= s.length(); ++i) {
        for (int j = 1; j <= p.length(); ++j) {
            if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?') {
                m[i][j] = m[i - 1][j - 1];
            } else if (p.charAt(j - 1) == '*') {
                m[i][j] = m[i][j - 1] || m[i - 1][j];
            }
        }
    }
    return m[s.length()][p.length()];
}