Interleaved Strings

JavaView on GFG

Time: O(n*m)

Space: O(n*m)

Intuition

DP: dp[i][j] = true if s1[0..i-1] and s2[0..j-1] can interleave to form s3[0..i+j-1].

Algorithm

1dp[0][0]=true.
2dp[i][j] = (dp[i-1][j] && s1[i-1]==s3[i+j-1]) || (dp[i][j-1] && s2[j-1]==s3[i+j-1]).

Common Pitfalls

•Length check: |s1|+|s2| must equal |s3|. 2D DP, not greedy.

Interleaved Strings.java

Java

// Approach: DP. dp[i][j] = can s1[0..i-1] and s2[0..j-1] interleave to form s3[0..i+j-1].
// Time: O(n*m) Space: O(n*m)
class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int n = s1.length();
        int m = s2.length();
        boolean[][] dp = new boolean[n + 1][m + 1];
        dp[n][m] = true;
        for (int i = n; i >= 0; i--) {
            for (int j = m; j >= 0; j--) {
                if (i < n && s1.charAt(i) == s3.charAt(i + j) && dp[i + 1][j])
                    dp[i][j] = true;
                else if (j < m && s2.charAt(j) == s3.charAt(i + j) && dp[i][j + 1])
                    dp[i][j] = true;
            }
        }
        
        return dp[0][0];
    }
}

Was this solution helpful?