Leetcode # 97. Interleaving String

Problem

len(s3) = len(s1) + len(s2)
set(s3) = set(s1) | set(s2) 

Solution: Backtracking + Memoization

重複子問題的例

1. s1: “aabcc”
   s2: “dbbca”
   s3: “aadbbbaccc”
2. s1: “aabcc”
   s2: “dbbca”
   s3: “aadbbbaccc”

Code

m := len(s1)
n := len(s2)

Time Complexity: O(m * n) (i, j 為自變數，k 為應變數)
Space Complexity: O(m * n) (memoization 需要的空間)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
    if len(s1) + len(s2) != len(s3): return False
    stack = [(0, 0, 0)]
    m, n = len(s1), len(s2)
    i_j_k = set()
    while stack:
      i, j, k = stack.pop()
      if (i, j, k) in i_j_k: 
        continue
      i_j_k.add((i, j, k))
      if k == len(s3): return True
      continuing = [True] * 2
      for d in range(max(m - i, n - j)):
        if continuing[0] and i + d < m and s1[i + d] == s3[k + d]:
          stack.append((i + d + 1, j, k + d + 1))
        else:
          continuing[0] = False
        if continuing[1] and j + d < n and s2[j + d] == s3[k + d]:
          stack.append((i, j + d + 1, k + d + 1))
        else:
          continuing[1] = False

    return False

Solution

dp[i][j] := s3[:i + j] can be an interleaving string of s1[:i] and s2[:j]

Time Complexity: O(m * n)
Space Complexity: O(min(m, n))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
    if len(s1) + len(s2) != len(s3): return False
    if len(s1)> len(s2): s1, s2 = s2, s1
    m, n = len(s1), len(s2)
    for i in range(m + 1):
      curr_dp = [False] * (n + 1)
      for j in range(n + 1):
        if i == j == 0:
          curr_dp[j] = True
        else:
          curr_dp[j] = \
            (i != 0 and s1[i - 1] == s3[i + j - 1] and prev_dp[j]) or \
            (j != 0 and s2[j - 1] == s3[i + j - 1] and curr_dp[j - 1])
      prev_dp = curr_dp

    return prev_dp[-1]

Last Updated on 2023/08/26 by A1go