Interleaving String

Interleaving String
https://leetcode.com/problems/interleaving-string/
给定三个字符串，s1,s2,s3，看s3是否由s1和s2穿插组成
Example 1:
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Example 2:
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false

解法一 超时啊，超时啊

    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1.isEmpty() && s2.isEmpty() && s3.isEmpty()) {
            return true;
        }
        //s3 为空，但是其他两个不为空，返回false
        if(s3.isEmpty()){
            return  false;
        }
        if (!s1.isEmpty() && s1.charAt(0) == s3.charAt(0)) {
            if (isInterleave(s1.substring(1), s2, s3.substring(1))) {
                return true;
            }
        }

        if (!s2.isEmpty() && s2.charAt(0) == s3.charAt(0)) {
            if (isInterleave(s1, s2.substring(1), s3.substring(1))) {
                return true;
            }
        }
        return false;
    }

解法二 跟解法一原理一样

多一个数组，去判断，每一位上已经判断过的条件，避免重复判断

public boolean isInterleave(String s1, String s2, String s3) {
        int memo[][] = new int[s1.length()][s2.length()];
        for (int i = 0; i < s1.length(); i++) {
            for (int j = 0; j < s2.length(); j++) {
                memo[i][j] = -1;
            }
        }
        return is_Interleave(s1, 0, s2, 0, s3, 0, memo);
    }

    public boolean is_Interleave(String s1, int i, String s2, int j, String s3, int k, int[][] memo) {
        if (i == s1.length()) {
            return s2.substring(j).equals(s3.substring(k));
        }
        if (j == s2.length()) {
            return s1.substring(i).equals(s3.substring(k));
        }
        if (memo[i][j] >= 0) {
            return memo[i][j] == 1 ? true : false;
        }
        boolean ans = false;
        if (s3.charAt(k) == s1.charAt(i) && is_Interleave(s1, i + 1, s2, j, s3, k + 1, memo)
                || s3.charAt(k) == s2.charAt(j) && is_Interleave(s1, i, s2, j + 1, s3, k + 1, memo)) {
            ans = true;
        }
        memo[i][j] = ans ? 1 : 0;
        return ans;
    }