Java Simple DP idea, clean code


  • 0
    A

    Just give some DP ideas, space complexity is not better than taht of two pointers algorithms.
    At the very beginning, I use a matrix to store the states, got Memory Limit Exceeded , code as follows

    public class Solution {
        public boolean isSubsequence(String s, String t) {
    
            if (s == null || s.isEmpty())
                return true;
            if (t == null || t.isEmpty())
                return false;
            char[] sArray = s.toCharArray();
            char[] tArray = t.toCharArray();
            int sizeS = s.length();
            int sizeT = t.length();
    
            boolean dp[][] = new boolean[sizeS + 1][sizeT + 1];
    
            for (int i = 0; i <= sizeT; ++i) {
                dp[0][i] = true;
            }
    
            for (int i = 1; i <= sizeS; ++i) {
                for (int j = 1; j <= sizeT; ++j) {
                    if (sArray[i - 1] == tArray[j - 1]) {
                        dp[i][j] = dp[i - 1][j -1];
                    }
                    else {
                        dp[i][j] = dp[i][j -1];
                    }
                }
            }
            return dp[sizeS][sizeT];
    
        }
    }
    

    So I reduced the matrix to array, passed, not fast code, just clean.

    public class Solution {
        public boolean isSubsequence(String s, String t) {
    
            if (s == null || s.isEmpty())
                return true;
            if (t == null || t.isEmpty())
                return false;
            char[] sArray = s.toCharArray();
            char[] tArray = t.toCharArray();
            int sizeS = s.length();
            int sizeT = t.length();
    
            boolean dp1[] = new boolean[sizeS + 1];
            boolean dp2[] = new boolean[sizeS + 1];
    
            dp1[0] = true;
            dp2[0] = true;
    
            for (int i = 1; i <= sizeT; ++i) {
                for (int j = 1; j <= sizeS; ++j) {
                    if (tArray[i - 1] == sArray[j - 1]) {
                        dp2[j] = dp1[j -1];
                    }
                    else {
                        dp2[j] = dp1[j];
                    }
                }
                // interchange two dp array
                boolean[] tmp = dp1;
                dp1 = dp2;
                dp2 = tmp;
    
            }
            return dp1[sizeS];
    
        }
    }
    

  • 0
    I

    Could you please explain why we need swap two dp arrrays. Thank you.


Log in to reply
 

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