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.

 

Approach 3: Using 2D Dynamic Programming

Algorithm

The recursive approach discussed in above solution included a character from one of the strings $s1$ or $s2$ in the resultant interleaved string and called a recursive function to check whether the remaining portions of $s1$ and $s2$ can be interleaved to form the remaining portion of $s3$. In the current approach, we look at the same problem the other way around. Here, we include one character from $s1$ or $s2$ and check whether the resultant string formed so far by one particular interleaving of the the current prefix of $s1$ and $s2$ form a prefix of $s3$.

Thus, this approach relies on the fact that the in order to determine whether a substring of $s3$(upto index $k$), can be formed by interleaving strings $s1$ and $s2$ upto indices $i$ and $j$ respectively, solely depends on the characters of $s1$ and $s2$ upto indices $i$ and $j$ only and not on the characters coming afterwards.

To implement this method, we'll make use of a 2D boolean array $dp$. In this array $dp[i][j]$ implies if it is possible to obtain a substring of length $(i+j+2)$ which is a prefix of $s3$ by some interleaving of prefixes of strings $s1$ and $s2$ having lengths $(i+1)$ and $(j+1)$ respectively. For filling in the entry of $dp[i][j]$, we need to consider two cases:

1. The character just included i.e. either at $i^{th}$ index of $s1$ or at $j^{th}$ index of $s2$ doesn't match the character at $k^{th}$ index of $s3$, where $k=i+j+1$. In this case, the resultant string formed using some interleaving of prefixes of $s1$ and $s2$ can never result in a prefix of length $k+1$ in $s3$. Thus, we enter $False$ at the character $dp[i][j]$.

2. The character just included i.e. either at $i^{th}$ index of $s1$ or at $j^{th}$ index of $s2$ matches the character at $k^{th}$ index of $s3$, where $k=i+j+1$. Now, if the character just included(say $x$) which matches the character at $k^{th}$ index of $s3$, is the character at $i^{th}$ index of $s1$, we need to keep $x$ at the last position in the resultant interleaved string formed so far. Thus, in order to use string $s1$ and $s2$ upto indices $i$ and $j$ to form a resultant string of length $(i+j+2)$ which is a prefix of $s3$, we need to ensure that the strings $s1$ and $s2$ upto indices $(i-1)$ and $j$ respectively obey the same property.

Similarly, if we just included the $j^{th}$ character of $s2$, which matches with the $k^{th}$ character of $s3$, we need to ensure that the strings $s1$ and $s2$ upto indices $i$ and $(j-1)$ also obey the same property to enter a $true$ at $dp[i][j]$.

This can be made clear with the following example:

s1="aabcc"
s2="dbbca"
s3="aadbbcbcac"

public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s3.length() != s1.length() + s2.length()) {
            return false;
        }
        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()];
    }
}    

Complexity Analysis
Time complexity : $O(m \cdot n)$. dp array of size $m*n$ is filled.
Space complexity : $O(m \cdot n)$. 2D dp of size $(m+1)*(n+1)$ is required. $m$ and $n$ are the lengths of strings $s1$ and $s2$ respectively.