LeetCode 97.交错字符串：记忆化解法超时问题优化求助

给定三个字符串s1、s2和s3，编写程序判断s3是否是s1和s2的交错字符串。

问题说明 #

如果s3包含s1和s2的所有字符，且单个字符串内的字符顺序保持不变，则称s3是s1和s2的交错字符串。

示例 #

示例1 #

• 输入：S1 = "xxyzz"，S2 = "wyyzx"，S3 = "xxwyyzyzxz"
• 输出：true
• 解释："xx"（来自S1） + "wyyz"（来自S2） + "yz"（来自S1） + "x"（来自S2） + "z"（来自S1）

示例2 #

• 输入：S1 = "xxyzz"，S2 = "wyyzx"，S3 = "xxwyyyxzzz"
• 输出：false
• 解释：无法通过交错S1和S2得到S3。

我已经用递归和记忆化方法解决了这个问题。递归会重复计算子问题，速度较慢，所以提交了记忆化实现的代码。代码通过了大部分测试用例，但最后一个测试用例超时（网站显示该用例本应通过）。我认为子串比较部分还没优化到位，导致运行速度不够，希望得到优化建议。

递归实现代码 #

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;
}

需要优化的记忆化实现代码 #

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;
}

示例输入代码 #

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);
}

内容的提问来源于stack exchange，提问作者curiousengineer