Yet another Java DP solution (O(N) space)


  • 0
    J

    The dp state start represents available starting index for next pattern.

    public boolean isMatch(String str, String pattern) {
        char[] strs = str.toCharArray();
        char[] pats = pattern.toCharArray();
        boolean[] start = new boolean[strs.length + 1];
        start[0] = true;
        for (int i = 0; i < pats.length; i++) {
            char p = pats[i];
            if (i < pats.length - 1 && pats[i + 1] == '*') {
                for (int j = 1; j <= strs.length; j++)
                    if (start[j - 1] && (p == '.' || p == strs[j - 1])) start[j] = true;
                i++;
            } else {
                for (int j = strs.length; j >= 1; j--) {
                    start[j] = start[j - 1] && (p == '.' || p == strs[j - 1]);
                }
                start[0] = false;
            }
        }
        return start[strs.length];
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.