題目出處

1143. Longest Common Subsequence

難度

medium

個人範例程式碼

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

        dp = [[0]*(n+1) for _ in range(m+1)]

        for i in range(1, m+1):
            for j in range(1, n+1):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1 # same case, update value form text[i-1][j-1]
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]) # default update

        return dp[-1][-1]

算法說明

經典的 LCS 問題，我們建表來進行搜索，
表格更新的邏輯為：

• 如果有字母相同，表示 text1, text2 一起移動：
  dp[i][j] = dp[i-1][j-1] + 1

• 其他情況(無字母相同)，只更新最大值：
  dp[i][j] = max(dp[i-1][j], dp[i][j-1])

input handling

一同在 dp 內處理。

Boundary conditions

用兩層 for 迴圈來控制範圍

Reference

• 最长公共子序列 · Longest Common Subsequence