97 Interleaving String

97. Interleaving String

1. Question

Givens1,s2,s3, find whethers3_is formed by the interleaving of_s1_and_s2.

Example 1:

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

Output: true

Example 2:

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

Output: false

2. Implementation

思路: 不管是用Memoization还是用DP做这题，我们都应该将这题转化成在一个2D矩阵里，行由s1的character排列而成(第一行的字符是空字符)，列(第一列的字符是空字符)由s2的character排列而成, 从(0,0) 到 (s1.length(), s2.length())的范围内，每次都只能往下或者右走，找出s3， 这样就有助于理解dp的推导公式和记忆化搜索为什么这么写

(1) DFS + Memoization

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) {
            return false;
        }

        Boolean[][] cache = new Boolean[s1.length() + 1][s2.length() + 1];

        return isInterleave(s1, s2, s3, 0, 0, cache);
    }

    public boolean isInterleave(String s1, String s2, String s3, int p1, int p2, Boolean[][] cache) {
        if (p1 + p2 == s3.length()) {
            return true;
        }

        if (cache[p1][p2] != null) {
            return cache[p1][p2];
        }

        boolean match1 = p1 < s1.length() && s1.charAt(p1) == s3.charAt(p1 + p2);
        boolean match2 = p2 < s2.length() && s2.charAt(p2) == s3.charAt(p1 + p2);
        boolean isValid = false;



        if (match1 && match2) {
            isValid = isInterleave(s1, s2, s3, p1 + 1, p2, cache) 
                   || isInterleave(s1, s2, s3, p1, p2 + 1, cache);
        }
        else if (match1) {
            isValid = isInterleave(s1, s2, s3, p1 + 1, p2, cache);
        }
        else if (match2) {
            isValid = isInterleave(s1, s2, s3, p1, p2 + 1, cache);
        }
        else {
            isValid = false;
        }
        cache[p1][p2] = isValid;
        return isValid;
    }
}

(2) DP

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) {
            return false;
        }

        int m = s1.length(), n = s2.length();
        boolean[][] dp = new boolean[m + 1][n + 1];

        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; 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[m][n];
    }
}

3. Time & Space Complexity

时间复杂度O(mn), m是s1的长度, n是s2的长度, 空间复杂度O(m + n)