97.Interleaving_String(Medium).md

97. Interleaving String (Medium)

Date and Time: Aug 27, 2024, 22:43 (EST)

Link: https://leetcode.com/problems/interleaving-string/

Question:

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.

Walk-through:

2D DP:

We can perform a quick sanity check to know if we should proceed checking by checking if len(s1) + len(s2) == len(s3).

1. Intialize a 2D DP table of size len(s1) + 1 * len(s2) + 1.

2. We first fill out the base cases, the first row by checking s1[i-1] = s3[i-1] and the first column by s2[j-1] = s3[j-1]. Remember to check and with its previous column or row if there is a match.

3. The rule to fill out the dp table is that
   i. we compare if s1[i-1] = s3[i+j-1] or s2[j-1] = s3[i+j-1].
   ii. If s1 or s2 has match, we need to check if its previous row or column is also True, so we can set current dp[i][j] = True. Otherwise, the interleaving substring we find will not be consistent.

4. Finally, we return the last entry of the dp table as our result, because it should match the last word in s3.

In the end, we will be able to find s3 by connecting the True from the dp to form s3.

    d b b c a
  T F F F F F
a T F F F F F
a T T T T T F
b F T T F T F
c F F T T T T
c F F F T F T

Python 2D DP Solution:

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        # aadbbcbcac
        #     d b b c a
        #   T F F F F F
        # a T
        # a T T T T T
        # b F       T
        # c F       T T
        # c F         T
        # 
        # r, c ptrs to keep track of 2 strings
        # Fill out the base case for first row/ first col
        # Recurrence Relation: 
        # Row: if s1[r-1] == s3[r+c-1] and dp[r-1][c] == True
        # Col: if s2[c-1] == s3[r+c-1] and dp[r][c-1] == True
        
        # TC: O(m x n), SC: O(m x n)
        rows, cols = len(s1), len(s2)
        dp = [[False] * (cols + 1) for _ in range(rows+1)]
        dp[0][0] = True     # Very base case
        # Fill out the base case row
        for c in range(1, cols+1):
            dp[0][c] = (s2[c-1] == s3[c-1]) and dp[0][c-1]
        # Fill out the base case col
        for r in range(1, rows+1):
            dp[r][0] = (s1[r-1] == s3[r-1]) and dp[r-1][0]

        # Build up the table top-bottom
        for r in range(1, rows+1):
            for c in range(1, cols+1):
                # Either a match from s1 or s2, also check prev row/col
                # Remember to check s1[r-1] instead of s1[r]
                dp[r][c] = (s1[r-1] == s3[r+c-1] and dp[r-1][c]) or (s2[c-1] == s3[r+c-1] and dp[r][c-1])
        
        return dp[-1][-1]

Time Complexity: $O(m * n)$, m is the length of s1, n is the length of s2.
Space Complexity: $O(m * n)$

Python 1D DP Solution:

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

        # Fill out the base case of the first row
        prev = [True] + [False] * len(s2)
        for c in range(1, len(s2)+1):
            prev[c] = prev[c-1] and (s2[c-1] == s3[c-1])
        
        for r in range(1, len(s1)+1):
            dp = [False] * (len(s2)+1)
            for c in range(len(s2)+1):
                dp[c] = (prev[c] and s1[r-1] == s3[r+c-1]) or (dp[c-1] and s2[c-1] == s3[r+c-1])
            prev = dp
        return prev[-1]

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

Slightly Optimized 1D DP Python Solution:

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

        dp = [True] + [False] * len(s2)
        for c in range(1, len(s2)+1):
            dp[c] = dp[c-1] and (s2[c-1] == s3[c-1])
        
        for r in range(1, len(s1)+1):
            dp[0] = dp[0] and s1[r-1] == s3[r-1]
            for c in range(1, len(s2)+1):
                dp[c] = (dp[c] and s1[r-1] == s3[r+c-1]) or (dp[c-1] and s2[c-1] == s3[r+c-1])

        return dp[-1]

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