97. Interleaving String

97. Interleaving String

Given strings s1, s2, and s3, find whether s3 is formed by an interleaving of s1 and s2.

An interleaving of two strings s and t is a configuration where they are divided into non-empty substrings such that:

• s = s1 + s2 + ... + sn

• t = t1 + t2 + ... + tm

• |n - m| <= 1

• The interleaving is s1 + t1 + s2 + t2 + s3 + t3 + ... or t1 + s1 + t2 + s2 + t3 + s3 + ...

Note: a + b is the concatenation of strings a and b.

Example 1:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true

Example 2:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false

Example 3:

Input: s1 = "", s2 = "", s3 = ""
Output: true

Constraints:

• 0 <= s1.length, s2.length <= 100

• 0 <= s3.length <= 200

• s1, s2, and s3 consist of lowercase English letters.

Follow up: Could you solve it using only O(s2.length) additional memory space?

My Solutions:

方法1： Recursion with memoization

i, j, k分别代表s1,s2,s3三个字符串的起始地址 （1）s3的首字母是来自s1吗？如果是，可以拆解为s1的 i+1 与 s2的j 与s3的Interleaving String子问题。 （2）s3的首字母是来自s2吗？如果是，可以拆解为s2的 j+1 与 s2的j 与s3的Interleaving String子问题。 以上2个条件成立一个，表示结果成立。 Base Case: 如果k超过了s3的length，表示s3是空串，返回TRUE 加一个二维矩阵来记录结果值，这样可以减少不必要的重复计算。

• Time complexity: O(m*n), where m is the length of s1 and n is the length of s2. That's a consequence of the fact that each (i, j) is computed only once.

• Space complexity: O(m*n) to keep the double array memo.

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) return false;
        
        int memo[][] = new int[s1.length()][s2.length()];
        // initialize all the number to -1
        for (int i = 0; i < s1.length(); i++) {
            for (int j = 0; j < s2.length(); j++) {
                memo[i][j] = -1;
            }
        }
        return getMemory(s1, 0, s2, 0, s3, 0, memo);
    }
    
    public boolean getMemory(String s1, int i, String s2, int j, String s3, int k, int[][] memo) {
        // if i is at the end of s1
        if (i == s1.length()) {
            return s2.substring(j).equals(s3.substring(k));
        }
        // if j is at the end of s2
        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) && getMemory(s1, i + 1, s2, j, s3, k + 1, memo))
                || (s3.charAt(k) == s2.charAt(j) && getMemory(s1, i, s2, j + 1, s3, k + 1, memo))
        ) {
            ans = true;
        }
        memo[i][j] = ans ? 1 : 0;
        return ans;
    }
}

方法2：Using 2D Dynamic Programming

D[i][j]: 定义为s1 (前i个字符) s2(前j个字符) s3(i+j 个字符) 是不是交叉字符

• s1 s3 首字母相同，继续查i -1 与 i + j -1 是否isInterleave

• s2 s3 首字母相同，继续查j -1 与 i + j -1 是否isInterleave

递推公式： (s1.i == s3.(i+j) && D[i-1][j]) || (s2.j == s3.(i+j) && D[i][j - 1])

• Time complexity: O(m*n). dp array of size m*n is filled.

• Space complexity: O(m*n). 2D dp of size (m+1)*(n+1) is required.

boolean dp[][] = new boolean[s1.length() + 1][s2.length() + 1];
for (int i = 0; i <= s1.length(); i++) {
    for (int j = 0; j <= s2.length(); j++) {
        if (i == 0 && j == 0) {
            dp[i][j] = true;
        } else if (i == 0) {
            dp[i][j] = dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1);
        } else if (j == 0) {
            dp[i][j] = dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1);
        } else {
            dp[i][j] = (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)) 
            || (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
        }
    }
}
return dp[s1.length()][s2.length()];

方法3：Using 1D Dynamic Programming

Use only 1D dp array to store the results of the prefixes of the strings processed so far. Instead of maintaining a 2D array, maintain a 1D array only and update the array's element dp[i] when needed using dp[i-1] and the previous value of dp[i].

boolean dp[] = new boolean[s2.length() + 1];
for (int i = 0; i <= s1.length(); i++) {
    for (int j = 0; j <= s2.length(); j++) {
        if (i == 0 && j == 0) {
            dp[j] = true;
        } else if (i == 0) {
            dp[j] = dp[j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1);
        } else if (j == 0) {
            dp[j] = dp[j] && s1.charAt(i - 1) == s3.charAt(i + j - 1);
        } else {
            dp[j] = (dp[j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)) || (dp[j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
        }
    }
}
return dp[s2.length()];