2D array solution then evolve to 1D space efficient one


  • 0
    H
    public class Solution {
        public boolean isMatch(String s, String p) {
            boolean[][] T = new boolean[s.length() + 1][p.length() + 1];
            T[0][0] = true;
            for (int i = 2; i < T[0].length; i++) {
                if (p.charAt(i - 1) == '*') {
                    T[0][i] = T[0][i - 2];
                }
            }
            for (int i = 1; i < T.length; i++) {
                for (int j = 1; j < T[0].length; j++) {
                    if (p.charAt(j - 1) == '.' || p.charAt(j - 1) == s.charAt(i - 1)) {
                        T[i][j] = T[i - 1][j - 1];
                    } else if (p.charAt(j - 1) == '*') {
                        T[i][j] = T[i][j - 2];
                        if (p.charAt(j - 2) == '.' || p.charAt(j - 2) == s.charAt(i - 1)) {
                            T[i][j] = T[i][j] | T[i - 1][j];
                        }
                    } else {
                        T[i][j] = false;
                    }
                }
            }
            return T[s.length()][p.length()];
        }
    }
    

    From solution above, we can tell a new T[i][j] depends on last row and current row's values which are T[i-1][j-1], T[i-1][j] and T[i][j-2].
    According to that, we can come out space efficient solution below:

    public class Solution {
        public boolean isMatch(String s, String p) {
            boolean[] T = new boolean[p.length() + 1];
            T[0] = true;
            for (int i = 2; i < T.length; i++) {
                if (p.charAt(i - 1) == '*') {
                    T[i] = T[i - 2];
                }
            }
            //leftUp stands for  T[i-1][j-1]
            //up stands for T[i-1][j]
            //prev2 stands for T[i][j-2]
            boolean leftUp, up, prev2;
            for (int i = 1; i <= s.length(); i++) {
                T[0] = false;
                leftUp  = i == 1 ? true : false;
                for (int j = 1; j <= p.length(); j++) {
                    up = T[j];
                    prev2 = j >= 2? T[j - 2] : false;
                    if (p.charAt(j - 1) == '.' || p.charAt(j - 1) == s.charAt(i - 1)) {
                        T[j] = leftUp;
                    } else if (p.charAt(j - 1) == '*') {
                        T[j] = prev2;
                        if (p.charAt(j - 2) == '.' || p.charAt(j - 2) == s.charAt(i - 1)) {
                            T[j] |= up;
                        }
                    } else {
                        T[j] = false;
                    }
                    leftUp = up;
                }
            }
            return T[p.length()];
        }
    }
    

Log in to reply
 

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