Leetcode # 1143. Longest Common Subsequence

https://leetcode.com/problems/longest-common-subsequence

Solution: Top-Down DP

Time Complexity: O(len(text1) * len(text2))
Space Complexity: O(len(text1) * len(text2))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def longestCommonSubsequence(self, text1: str, text2: str) -> int:
    global dp
    dp      = {(i, 0): 0 for i in range(len(text1) + 1)}
    dp.update({(0, j): 0 for j in range(len(text2) + 1)})
    # ...
    def lcs(stop1, stop2):
      if (stop1, stop2) not in dp:
        # ...
        dp[(stop1, stop2)] = (lcs(stop1 - 1, stop2 - 1) + 1) \
                               if text1[stop1 - 1] == text2[stop2 - 1] \
                               else max(lcs(stop1, stop2 - 1), lcs(stop1 - 1, stop2))
      return dp[(stop1, stop2)]
    return lcs(len(text1), len(text2))

Solution: Button-Up DP (Space Complexity: O(max(n1, n2)))

n1 := len(text1)
n2 := len(text2)

Time Complexity: O(n1 * n2)
Space Complexity: O(max(n1, n2))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def longestCommonSubsequence(self, text1: str, text2: str) -> int:
    length = max(len(text1), len(text2))
    # base cases
    dp      = {(i, 0): 0 for i in range(length + 1)}
    dp.update({(0, j): 0 for j in range(length + 1)})
    for l in range(1, length + 1):
      cur_dp = {}
      for i in range(l, length + 1):
        cur_dp[(i, l)] = (dp[(i - 1, l - 1)] + 1) \
                           if i <= len(text1) and l <= len(text2) \
                             and text1[i - 1] == text2[l - 1] \
                           else max(cur_dp[(i - 1, l)] if i > l else dp[(i - 1, l)], 
                                    dp[(i, l - 1)])
      for j in range(l, length + 1):
        cur_dp[(l, j)] = (dp[(l - 1, j - 1)] + 1) \
                           if l <= len(text1) and j <= len(text2) \
                             and text1[l - 1] == text2[j - 1] \
                           else max(dp[(l - 1, j)], 
                                    cur_dp[(l, j - 1)] if j > l else dp[(l, j - 1)])
      dp = cur_dp
      if (len(text1), len(text2)) in dp:
        return dp[(len(text1), len(text2))]

space complexity 還可以再更小

由於我們算 dp[i] 只需要 dp [i – 1]
所以我們令
_text1 := [text1, text2][0 if len(text1) > len(text2) else 1]
_text2 := [text1, text2][0 if len(text1) < len(text2) else 1]
_n1 := max(len(text1), len(text2))
_n2 := min(len(text1), len(text2))

prev_dp := dp[i – 1]
curr_dp := dp[i]
len(prev_dp) == len(curr_dp) == _n2 + 1

用 i = [1, _n1] 的 for 迴圈計算 dp[i]
在 i = [1, _n1] 的 for 迴圈中用 j = [1, _n2] 的 for 迴圈計算 dp[i][j]
(計算 dp[i][j] 時，dp[i – 1], dp[i][j – 1] 已計算完畢)

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

class Solution:
  def longestCommonSubsequence(self, text1: str, text2: str) -> int:
    if len(text1) < len(text2):
      text1, text2 = text2, text1

    # base cases
    prev_dp = [0] * (len(text2) + 1)
    for i in range(1, len(text1) + 1):
      curr_dp = [0] * (len(text2) + 1)
      for j in range(1, len(text2) + 1):
        curr_dp[j] = (prev_dp[j - 1] + 1) \
                    if text1[i - 1] == text2[j - 1] \
                    else max(prev_dp[j], curr_dp[j - 1])
      prev_dp = curr_dp
    return prev_dp[-1]

Last Updated on 2023/08/16 by A1go