Skip to content
AI360Xpert
Back to 2-D Dynamic Programming
Medium

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`.

Examples

Input:s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output:true
One way to obtain s3 is: Split s1 into "aa" + "bc" + "c", and s2 into "dbbc" + "a". Interleaving the two splits, we get "aa" + "dbbc" + "bc" + "a" + "c" = "aadbbcbcac". Since s3 can be obtained by interleaving s1 and s2, we return true.
Input:s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output:false
Notice how it is impossible to interleave s1 and s2 to form s3.
Input:s1 = "", s2 = "", s3 = ""
Output:true
Empty strings are interleaved to form an empty string.

Constraints

  • 0 <= s1.length, s2.length <= 100
  • 0 <= s3.length <= 200
  • s1, s2, and s3 consist of lowercase English letters.

Dynamic Programming (2D Array)

Approach

First, check if `s1.length + s2.length == s3.length`. If not, it's impossible. We can use a 2D DP array `dp` where `dp[i][j]` is true if `s1[0...i-1]` and `s2[0...j-1]` can interleave to form `s3[0...i+j-1]`. We can transition to `dp[i][j]` from: - `dp[i-1][j]` if the `i`th character of `s1` matches the `(i+j)`th character of `s3`. - `dp[i][j-1]` if the `j`th character of `s2` matches the `(i+j)`th character of `s3`. We iterate from the end of the strings to the beginning.

Complexity Analysis

Time Complexity
O(m * n)
Space Complexity
O(m * n)

m and n are the lengths of s1 and s2. The DP table is of size (m+1) x (n+1). This can be space-optimized to O(n) by only keeping the current and previous rows.

Solution.java
class Solution {    public boolean isInterleave(String s1, String s2, String s3) {        if (s1.length() + s2.length() != s3.length()) {            return false;        }                int m = s1.length();        int n = s2.length();        boolean[][] dp = new boolean[m + 1][n + 1];                // Base case: empty strings form empty string        dp[m][n] = true;                for (int i = m; i >= 0; i--) {            for (int j = n; j >= 0; j--) {                // Check if character from s1 matches character from s3                if (i < m && s1.charAt(i) == s3.charAt(i + j) && dp[i + 1][j]) {                    dp[i][j] = true;                }                // Check if character from s2 matches character from s3                if (j < n && s2.charAt(j) == s3.charAt(i + j) && dp[i][j + 1]) {                    dp[i][j] = true;                }            }        }                return dp[0][0];    }}