44. Wildcard Matching

二刷
Seems like match one 的case可以被省略
感觉是 match one 可以被match multiple 给cover掉

14.18 %
class Solution {
    public boolean isMatch(String s, String p) {
        if (s == null && p == null) return true;
        if (s == null || p == null) return false;
        // * matches any substring
        boolean[][] dp = new boolean[s.length() + 1][p.length() + 1]; // match result of s[0, i) with p[0, j)
        dp[0][0] = true;
        // p s = " a c d c b"
        //""
        // a       T F 
        // *       T   
        // c
        // ?
        // b
        // when dp[i][0] always false since pattern is empty
        // i = 0
        for (int j = 1; j <= p.length(); j++) {
            if (p.charAt(j - 1) == '*') {
                dp[0][j] = dp[0][j - 1];
            }
        }
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 1; j <= p.length(); j++) {
                if (p.charAt(j - 1) == '*') {
                    //         match zero      match one           match several
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j - 1] || dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j - 1]
                        && (p.charAt(j - 1) == '?' || s.charAt(i - 1) == p.charAt(j - 1));
                }
            }
        }
        return dp[s.length()][p.length()];
    }
}


一刷
反正我是不是很懂
初始化比较关键，注释里面写了
关于为什么
} else if (pChar == '*') {
                    dp[sIndex][pIndex] = dp[sIndex - 1][pIndex] || dp[sIndex][pIndex - 1];
我并不懂啊

public class Solution {
    public boolean isMatch(String s, String p) {
        if (s == null || p == null) throw new IllegalArgumentException();
        int sLength = s.length();
        int pLength = p.length();
        boolean[][] dp = new boolean[sLength + 1][pLength + 1];
        dp[0][0] = true;
        //dp[sIndex][pIndex]
        //when pIndex == 0, default to false
        //when sIndex == 0, trying to match empty string
        for (int pIndex = 1; pIndex <= pLength; pIndex++) {
            dp[0][pIndex] = dp[0][pIndex - 1] && p.charAt(pIndex - 1) == '*';
        }
        //System.out.println(0 + " " + 0 + " " + dp[0][0]);
        for (int pIndex = 1; pIndex <= pLength; pIndex++) {
            for (int sIndex = 1; sIndex <= sLength; sIndex++) {
                char pChar = p.charAt(pIndex - 1);
                char sChar = s.charAt(sIndex - 1);
                if (pChar == '?' || pChar == sChar) {
                    dp[sIndex][pIndex] = dp[sIndex - 1][pIndex - 1];
                } else if (pChar == '*') {
                    dp[sIndex][pIndex] = dp[sIndex - 1][pIndex] || dp[sIndex][pIndex - 1];
                } else {
                    dp[sIndex][pIndex] = false;
                }
                //System.out.println(sIndex + " " + pIndex + " " + dp[sIndex][pIndex]);
            }
        }
        return dp[sLength][pLength];
    }
}


Version #1 DFS
TLE
public class Solution {
    public boolean isMatch(String s, String p) {
        if (s == null || p == null) throw new IllegalArgumentException();
        return isMatch(s, p, 0, 0);
    }
    private boolean isMatch(String s, String p, int sIndex, int pIndex) {
        if (pIndex == p.length()) return sIndex == s.length();
        if (p.charAt(pIndex) != '*') {
            if (sIndex >= s.length()) return false;
            if (p.charAt(pIndex) == '?' || s.charAt(sIndex) == p.charAt(pIndex)) {
                return isMatch(s, p, sIndex + 1, pIndex + 1);
            } else return false;
        } else {
            while (sIndex <= s.length()) {
                if (isMatch(s, p, sIndex, pIndex + 1)) return true;
                sIndex++;
            }
        }
        return false;
    }
}