97. Interleaving String

time: O(m*n), m is s1 length, n is s2 length

space: O(mn

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length();
        int n = s2.length();
        if (m+n != s3.length()) {
            return false;
        }
        
        boolean dp[][] = new boolean[m+1][n+1];
            
        s1 = "#" + s1;
        s2 = "#" + s2;
        s3 = "#" + s3;
        
        dp[0][0] = true; // all empty, s1+s2 == s3
        
        // 根據題意, 只要能交迭出 s3, 就是 true, 所以 s2 = "", 其實就是要要 s1 == s3
        // 所以從最後一位開始推是否相等
        for (int i = 1; i <= m; i++) {
            dp[i][0] = dp[i-1][0] && s1.charAt(i) == s3.charAt(i);
        }
        for (int j = 1; j <= n; j++) {
            dp[0][j] = dp[0][j-1] && s2.charAt(j) == s3.charAt(j);
        }
        
        // 能交迭出, 就是s1 or s2 某字串的最後一位必定在 s3 最後一位
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (dp[i-1][j] && s1.charAt(i) == s3.charAt(i+j)) {
                    dp[i][j] = true;
                }
                if (dp[i][j-1] && s2.charAt(j) == s3.charAt(i+j)) {
                    dp[i][j] = true;
                }
            }
        }
        return dp[m][n];
    }
}

DFS + memo

1 ms, faster than 99.10% of Java online submissions for Interleaving String.

T: O(mn)

S: O(mn)

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) {
            return false;
        }
        return dp(s1,s2,s3, 0, 0, new Boolean[s1.length()+1][s2.length()+1]);
    }
    private boolean dp(String s1, String s2, String s3, int i, int j, Boolean[][] memo) {
        int m = s1.length();
        int n = s2.length();
        int k = s3.length();
        if (i + j == k) {
            return true;
        }
        if (memo[i][j] != null) {
            return memo[i][j];
        }
        boolean result = false;
        if (i < m && s3.charAt(i+j) == s1.charAt(i) && dp(s1,s2,s3,i+1, j, memo)) {
            result = true;
        }
        if (j < n && s3.charAt(i+j) == s2.charAt(j) && dp(s1,s2,s3,i, j+1, memo)) {
            result = true;
        }
        return memo[i][j] = result;
    }
    
}

or use ||, this one is easy to convert to 1D

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length();
        int n = s2.length();
        if (m + n != s3.length()) {
            return false;
        }
        boolean[][] dp = new boolean[m+1][n+1];
        s1 = "#" + s1;
        s2 = "#" + s2;
        s3 = "#" + s3;
        
        dp[0][0] = true;
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i > 0) {
                    dp[i][j] = dp[i][j] || dp[i-1][j] && s1.charAt(i) == s3.charAt(i + j);
                }
                if (j > 0) {   
                    dp[i][j] = dp[i][j] || dp[i][j-1] && s2.charAt(j) == s3.charAt(i + j);
                }
                
            }
        }
        return dp[m][n];
    }
}

1D

T: O(mn)

S: O(n)

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length();
        int n = s2.length();
        if (m + n != s3.length()) {
            return false;
        }
        boolean[] dp = new boolean[n+1];
        s1 = "#" + s1;
        s2 = "#" + s2;
        s3 = "#" + s3;
        
        dp[0] = true;
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i > 0) {
                    dp[j] = dp[j] && s1.charAt(i) == s3.charAt(i + j);
                }
                if (j > 0) {   
                    dp[j] = dp[j] || dp[j-1] && s2.charAt(j) == s3.charAt(i + j);
                }
                
            }
        }
        return dp[n];
    }
}


/*
for (int i=1)
  for (int j = 1)
if (i > 0) {
    dp[i][j] = dp[i][j] || dp[i-1][j] && s1.charAt(i) == s3.charAt(i + j);
}
if (j > 0) {   
    dp[i][j] = dp[i][j] || dp[i][j-1] && s2.charAt(j) == s3.charAt(i + j);
}


      j1 
      0,1 0,2 0,3
i1        1,2

case1
if (i > 0) {  depends on J move => so same i, move j
dp[1][1] = dp[0][1] && ...
dp[1][2] = dp[0][2] && ...
if (i > 0) {
    dp[j] = dp[j] && s1.charAt(i) == s3.charAt(i + j);
}


case2
dp[1][1] = dp[1][0] &&...
dp[1][2] = dp[1][1] &&
if (j > 0) {  dp[j] depends dp[j-1]
    dp[j] = dp[j] || dp[j-1] && s2.charAt(j) == s3.charAt(i + j);
}
*/