[Q][Why] DP solution is slower than DFS solution with cache array?


  • 0

    I always have the mindset that DP is always clean, clear and faster, however, after solving this question, I find I am wrong.
    1.I first solve this question with a pure DFS solution which is definitely timeout, as we recursively visited many duplicated cases.

    public static boolean isInterleaveRec(String s1, String s2, String s3, int i, int j, int k) {
    if (i == s1.length() && j == s2.length() && k == s3.length())
                return true;
    
            boolean validS1 = false;
            boolean validS2 = false;
            if (i < s1.length() && s1.charAt(i) == s3.charAt(k))
                validS1 = isInterleaveRec(s1, s2, s3, i + 1, j, k + 1);
            if (j < s2.length() && s2.charAt(j) == s3.charAt(k))
                validS2 = isInterleaveRec(s1, s2, s3, i, j + 1, k + 1);
            return validS1 || validS2;
    }
    
    1. Then I think of using an array to cache some cases, so if we have the result already, we do not need to enter the iteration, which is super fast, only take 2ms and beats 90%
    public static boolean isInterleaveMemo(String s1, String s2, String s3, int i, int j, int k, int[][] valid) {
            if (valid[i][j] != -1)
                return valid[i][j] == 1;
    
            if (i == s1.length() && j == s2.length() && k == s3.length())
                return true;
    
            boolean validS1 = false;
            boolean validS2 = false;
            if (i < s1.length() && s1.charAt(i) == s3.charAt(k))
                validS1 = isInterleaveMemo(s1, s2, s3, i + 1, j, k + 1, valid);
            if (j < s2.length() && s2.charAt(j) == s3.charAt(k))
                validS2 = isInterleaveMemo(s1, s2, s3, i, j + 1, k + 1, valid);
            valid[i][j] = validS1 || validS2 == true ? 1 : 0;
            return validS1 || validS2;
        }
    
    1. Then I think yeah I can do it in DP way
     public static boolean isInterleaveDP(String s1, String s2, String s3) {
     boolean[] valid = new boolean[s2.length() + 1];
            
            //for i==0 and j==0 initial the value with s1 match s3 or s2 mathc s3
            valid[0]=true;
            for (int i = 0; i <= s1.length(); i++) {
                if (i == 0) { //initial
                    for (int j = 1; j <= s2.length(); j++)
                        valid[j] = valid[j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1);
                }
                for (int j = 0; i!=0&&j <= s2.length(); j++) {
                    if (j == 0) { //initial
                      valid[j] = valid[j] && s1.charAt(i - 1) == s3.charAt(i + j - 1);
                    } else {
                        //valid[j-1] means s1(0,i) s2(0,j-1) is match with s3 ,we want to know if s2(0,j) is continually matched with s3
                        //valid[j] means s1(0,i-1) s2(0,j) is match with s3, we want ot know if s1(0,i) is match with s3
                        valid[j] = valid[j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1) || valid[j] && s1.charAt(i - 1) == s3.charAt(i + j - 1);
                    }
                }
            }
            return valid[s2.length()];
    }
    

    but DP solution take 4ms which only beats 55%

    [Q]: what's going on? Is there any improvement I can do for my DP code? or is this a demonstration that DP is not absolutely faster?


Log in to reply
 

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