Further optimization to the algo for interleaving string

Question

I am trying to solve LeetCode problem 97. Interleaving String :

Given three strings s1, s2 and s3, write a program that checks whether s3 is an interleaving of s1 and s2.

Problem Note:

S3 is said to be interleaving S1 and S2 if it contains all characters of S1 and S2 and the order of all characters in individual strings is preserved.

Example 1:

• Input: S1 = "xxyzz", S2 = "wyyzx" and S3 = "xxwyyzyzxz"
• Output: true
• Explanation: "xx" (from S1) + "wyyz" (from S2) + "yz" (from S1) + "x" (from S2) + "z" (from S1)

Example 2:

• Input: S1 = "xxyzz", S2 = "wyyzx", S3 = "xxwyyyxzzz"
• Output: false
• Explanation: It is not possible to get S3 by interleaving S1 and S2.

I solved it with recursion and memoization. The recursion re-computing subproblems is slower, so I submitted my solution with memoization. It passes all test cases and right at the last test case -- which does pass as per the website -- I still get time limit exceeded. I believe there is a substring comparison snippet in my code that I am still not optimizing that can make the code run faster. Any suggestions will be helpful.

Here is the code with recursion (I am looking for help on the one with memoization)

     public static boolean interleave(String s1, String s2, String s3,
                                     int i1, int i2, int i3) {
        if(i1<0) {
            return s2.substring(0,i2+1).equals(s3.substring(0,i3+1));
        }

        if(i2<0) {
           return s1.substring(0,i1+1).equals(s3.substring(0,i3+1));
        }

        boolean s1path = s1.charAt(i1) == s3.charAt(i3) &&
                interleave(s1,s2,s3,i1-1,i2,i3-1);
        boolean s2path = s2.charAt(i2) == s3.charAt(i3) &&
                interleave(s1,s2,s3,i1,i2-1,i3-1);
        return s1path || s2path;
    }

Here is the code with memoization that requires a bit of optimization that I am unable to do

    public static boolean interleavememo(String s1, String s2, String s3,
                                     int i1, int i2, int i3, int[][]dp) {
        if(i1<0) {
            var r = s2.substring(0,i2+1).equals(s3.substring(0,i3+1));
            return r;
        }

        if(i2<0) {
            var r = s1.substring(0,i1+1).equals(s3.substring(0,i3+1));
            return r;
        }

        var val = dp[i1][i2];
        if(val == 1) return true;
        if(val == 0) return false;

        boolean s1path = s1.charAt(i1) == s3.charAt(i3) &&
                interleavememo(s1,s2,s3,i1-1,i2,i3-1, dp);
        boolean s2path = s2.charAt(i2) == s3.charAt(i3) &&
                interleavememo(s1,s2,s3,i1,i2-1,i3-1,dp);
        boolean result = s1path||s2path;
        if(result) {
            dp[i1][i2] = 1;
        }
        return result;
    }

Example input

    public static void main(String[] args) {
        var s1 = "ABC";
        var s2 = "ACD";
        var s3 = "ACDABC";
        var i1 = s1.length()-1;
        var i2 = s2.length()-1;
        var i3 = s3.length()-1;
        var dp = new int[s1.length()][s2.length()];
        for(int i = 0; i<dp.length; i++) {
            Arrays.fill(dp[i],-1);
        }
        var retval = interleavememo(s1,s2,s3, i1, i2, i3, dp);

        System.out.println(retval);
    }

Answer 1

Your memoization code only lacks a few things:

• I didn't see any code that checks whether the size of s3 is the sum of the sizes of the other two strings. If this basic condition is not true, you should immediately return false.

• The memoization should happen also when you don't have success. There is no code where you store the value 0. Memoization of failure is just as valuable as the memoization of success.

• If you have success with the first recursive call, you shouldn't make the second recursive call. You can use the principle of short-cut evaluation for this and put both expressions in one expression.

Here is the corrected code:

    public boolean isInterleave(String s1, String s2, String s3) {
        var i1 = s1.length();
        var i2 = s2.length();
        var i3 = s3.length();
        // Make sure it is even possible, based on lengths:
        if (i1 + i2 != i3) return false; // Quick exit
        var dp = new int[i1][i2];
        for(int i = 0; i < dp.length; i++) {
            Arrays.fill(dp[i], -1);
        }
        var retval = interleavememo(s1, s2, s3, i1 - 1, i2 - 1, i3 - 1, dp);
        return retval;
    }

    public static boolean interleavememo(String s1, String s2, String s3,
                                         int i1, int i2, int i3, int[][]dp) {
        if (i1 < 0) {
            var r = s2.substring(0, i2 + 1).equals(s3.substring(0, i3 + 1));
            return r;
        }
        if (i2 < 0) {
            var r = s1.substring(0, i1 + 1).equals(s3.substring(0, i3 + 1));
            return r;
        }
        var val = dp[i1][i2];
        if (val != -1) return val == 1; // combine both cases in one exit point.

        // Use shortcut evaluation
        boolean result = s1.charAt(i1) == s3.charAt(i3) &&
                    interleavememo(s1, s2, s3, i1 - 1, i2, i3 - 1, dp)
                || s2.charAt(i2) == s3.charAt(i3) &&
                    interleavememo(s1, s2, s3, i1, i2 - 1, i3 - 1,dp);
        // Whatever the result, store it; not only when success
        dp[i1][i2] = result ? 1 : 0;
        return result;
    }