# Leetcode 97. Interleaving String

[link](https://leetcode.com/problems/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 s and t are divided into n and m
substrings
respectively, 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
Explanation: One way to obtain s3 is:
Split s1 into s1 = "aa" + "bc" + "c", and s2 into s2 = "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.

Example 2:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false
Explanation: Notice how it is impossible to interleave s2 with any other string to obtain s3.

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.

---

Check if the combined length of s1 and s2 is not equal to the length of s3. If they are not of the same length, return False because it's impossible to form s3 by interleaving s1 and s2.

Create a 2D dynamic programming table dp where each cell dp[i][j] represents whether the first i characters of s1 and the first j characters of s2 can be interleaved to form the first i + j characters of s3. Initialize dp[len(s1)][len(s2)] to True because empty strings can be formed by interleaving two empty strings.

Iterate through the dp table in reverse order, starting from the bottom-right corner and moving towards the top-left corner. This allows you to build up the interleave possibilities for larger substrings based on the values already computed for smaller substrings.

For each cell (i, j) in the dp table, check two conditions:

If i is within the bounds of s1, and the character in s1 at position i is equal to the character in s3 at position i + j, and dp[i + 1][j] is True, then set dp[i][j] to True. This means that we can interleave s1 and s2 to form s3 up to position i + j.
Similarly, if j is within the bounds of s2, and the character in s2 at position j is equal to the character in s3 at position i + j, and dp[i][j + 1] is True, then set dp[i][j] to True. This means that we can interleave s1 and s2 to form s3 up to position i + j.

Finally, return the value in the top-left corner of the dp table, which represents whether we can interleave s1 and s2 to form s3.

#### Solution 1

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        if len(s1) + len(s2) != len(s3):
            return False

        dp = [[False] * (len(s2) + 1) for _ in range(len(s1) + 1)]
        dp[len(s1)][len(s2)] = True
        
        for i in range(len(s1), -1, -1):
            for j in range(len(s2), -1, -1):
                if i < len(s1) and s1[i] == s3[i + j] and dp[i + 1][j]:
                    dp[i][j] = True
                if j < len(s2) and s2[j] == s3[i + j] and dp[i][j + 1]:
                    dp[i][j] = True

        return dp[0][0]
        

O(T): O(m * n)
O(S): O(m * n)

---

It checks if the combined length of s1 and s2 is equal to the length of s3. If not, it returns False because it's impossible to form s3 by interleaving.

The code uses a recursive function dfs(i, j) to explore different interleaving possibilities. The function checks if characters from s1 and s2 can be interleaved to match s3 starting from positions i and j, respectively.

To avoid redundant calculations, it employs memoization by storing intermediate results in a dictionary (dp). If the result for a particular pair of indices (i, j) has already been calculated, it's retrieved from the dictionary instead of recomputing it.

The dfs function checks conditions to see if characters from s1 and s2 match characters in s3. If they do, it recursively calls itself with updated indices to continue checking the next characters.

If none of the conditions in the dfs function are met, it sets the result to False for the current (i, j) pair.

The final result is obtained by initiating the recursive process with dfs(0, 0) to check if it's possible to interleave s1 and s2 to form s3.

#### Solution 2

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        if len(s1) + len(s2) != len(s3):
            return False

        dp = {}
        def dfs(i, j):
            if i == len(s1) and j == len(s2):
                return True
            
            if (i, j) in dp:
                return dp[(i, j)]
            
            if i < len(s1) and s1[i] == s3[i + j] and dfs(i + 1, j):
                return True

            if j < len(s2) and s2[j] == s3[i + j] and dfs(i, j + 1):
                return True
            
            dp[(i, j)] = False
            
            return False
        
        return dfs(0, 0)

O(T): O(m * n)
O(S): O(m * n)