Short Java O(k) space DP solution beats 99,5%


  • 1
    A

    Reduced the space of most top answers from O(nk) to O(k). (n = length of s, k = length of pattern)

    Thinking as if it was a 2D array, the dp[i][j] holds whether the substring 0..i of s does match substring 0..j of p. So start at dp[0][0] and iterate. At each step update all substring / subpattern pairs that can be reached from current substring / subpattern position. There are only 3 pairs possibly reachable.

    When checking a position, you can either consume a char that matches the pattern (exact match or match .) and move both forward.
    OR
    when pattern is followed by * then you have two options:

    • ignore x*, just go ahead in pattern
    • consume a char in s and stay in pattern
        public boolean isMatch(String s, String p) {
            boolean[] pre = new boolean[p.length()+1];
            boolean[] next = new boolean[p.length()+1];
            pre[0] = true;
            for (int sI = 0; sI <= s.length(); sI++) {
                for (int pI = 0; pI < p.length(); pI++) {
                    if (!pre[pI]) continue; // you can't go anywhere from here
                    if (pI < p.length() - 1 && p.charAt(pI+1) == '*') { // look ahead if pI not at the end
                        pre[pI+2] |= pre[pI];  // skip x*
                        if (sI < s.length() && (s.charAt(sI) == p.charAt(pI) || p.charAt(pI) == '.')) {
                            next[pI] |= pre[pI]; // consume x, stay in pattern
                        }
                    } else if (sI < s.length() && (s.charAt(sI) == p.charAt(pI) || p.charAt(pI) == '.')) {
                        next[pI+1] |= pre[pI]; // consume x, move pattern
                    }
                }
                pre = sI == s.length()? pre : next;
                next = new boolean[p.length()+1]; 
            }
            return pre[p.length()];
        }
    

  • 0
    A

    @A1m Nice and elegant solution. One question though, what's the meaning of the following two lines?
    pre = sI == s.length()? pre : next;
    next = new boolean[p.length()+1];
    I don't quite follow. Hope you could explain, thank you!


  • 1
    A

    Each line you are progressing your 2 arrays to the next level by setting prev to next and init an empty next.

    The sI == s.length()? check is just there for the very last iteration, you can't throw away your pre, since the result is pre[p.length()];

    Notice that for the very last iteration, only things in pre change cause of that condition sI < s.length() &&. next is just empty in the last iteration.


Log in to reply
 

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