My DP solution, but got TLE in space. any idea.


  • 0
    J

    got TLE in space. anyone knows why?

    
        public boolean isSubsequence(String s, String t) {
            int m=s.length();
            int n=t.length();
            boolean[][]dp=new boolean[m+1][n+1];
            for(int i=0;i<n+1;i++){
                dp[0][i]=true;
            }
            for(int i=0;i<m+1;i++){
                dp[i][0]=false;
            }
            dp[0][0]=true;
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    dp[i+1][j+1]=(s.charAt(i)==t.charAt(j)&&dp[i][j])||dp[i+1][j];
                }
            }
            return dp[m][n];
        }
    

  • 1
    T

    Same here. Got MLE with classical way of DP solution. Since here the (i, j) problem is only related to (i-1, j-1) or (i-1, j) problem, you can use a rolling array instead of a whole matrix. The trick is, you still define the dp matrix as you always did, except making the row length to be 2, and take a modulo of 2 when you update dp state. Also, use s's length as column length will help you, because the question says that t's length can be very large. So now the memory usage will only be two arrays of s's length.

    public class Solution {
        public boolean isSubsequence(String s, String t) {
            // check edge case
            if (s == null || t == null) {
                return true;
            }
            // preprocess
            int sLen = s.length();
            int tLen = t.length();
            // dp def
            boolean[][] dp = new boolean[2][sLen + 1];
            // dp init
            dp[0][0] = true;
            for (int j = 1; j <= sLen; j++) {
                dp[0][j] = false;
            }
            // dp transition
            for (int i = 1; i <= tLen; i++) {
                for (int j = 0; j <= sLen; j++) {
                    if (j == 0) {
                        dp[i % 2][0] = true;
                        continue;
                    }
                    char tCh = t.charAt(i - 1);
                    char sCh = s.charAt(j - 1);
                    if (sCh == tCh) {
                        dp[i % 2][j] |= dp[(i-1) % 2][j-1];
                    }
                    dp[i % 2][j] |= dp[(i - 1) % 2][j];
                }
            }
            return dp[tLen % 2][sLen];
        }
    }
    

Log in to reply
 

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