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

Intuitive Solution (TLE)

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        # Q: Check if s3 can be completely composed by s1 and s2
        # S: 1. Use two ptrs for s1[i] and s2[j], if any of the char matches the one in s3[k], use it and advance ptr
        # 2. If not matches chars from s1 and s2, return False
        # 3. Check if i, j are in the end
        # TC: O(2^n), n=len(s3), SC: O(n)

        def backtrack(i, j, k):
            if k == len(s3):
                if i == len(s1) and j == len(s2):
                    return True
                else:
                    return False
            # If matches char, we should advance the ptr to next char
            if i < len(s1) and s3[k] == s1[i]:
                if backtrack(i+1, j, k+1):
                    return True
            if j < len(s2) and s3[k] == s2[j]:
                if backtrack(i, j+1, k+1):
                    return True
            return False
        return backtrack(0, 0, 0)

Time Complexity: $O(2^{m+n})$, m is the length of s1, n is the length of s2.
Space Complexity: $O(m+n)$ for recursion stack

Memoization from previous solutioin

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        # Q: Check if s3 can be completely composed by s1 and s2
        # S: 1. Use two ptrs for s1[i] and s2[j], if any of the char matches the one in s3[k], use it and advance ptr
        # 2. If not matches chars from s1 and s2, return False
        # 3. Check if i, j are in the end
        # Use memoization to for s2 length
        # TC: O(mxn), m=len(s1), n=len(s2), SC: O(mxn)

        dp = {}     # {(i,j,k): true/false}
        def backtrack(i, j, k):
            # Save (i, j, k) as dp key, value should be true or false
            if k == len(s3):
                if i == len(s1) and j == len(s2):
                    return True
                else:
                    return False
            # Base case to fetch cached results
            if (i, j, k) in dp:
                return dp[(i,j,k)]
            # If matches char, we should advance the ptr to next char
            results = False
            if i < len(s1) and s3[k] == s1[i]:
                results = backtrack(i+1, j, k+1)
            # If (i+1) does not lead to true
            if not results and j < len(s2) and s3[k] == s2[j]:
                results = backtrack(i, j+1, k+1)
            # Cache results for (i, j, k)
            dp[(i,j,k)] = results
            return results
        return backtrack(0, 0, 0)

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

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)$