LeetCode 1143: Longest Common Subsequence ·

基本資料
#

難易度: medium 第一次嘗試：2026-07-11 來源：Day 36 learning note

學習脈絡
#

這篇是從 learning note 裡該 LeetCode 題目的段落重新整理出來的版本。我保留當天筆記中的修正點、比較點、容易犯錯的地方，並移除同一天其他非 LeetCode 主題，避免文章內容混題。

筆記中提到的相關提醒
#

LC 1143: pass after mismatch-proof wording repair
explain LC 1143 with exact prefix-based state and mismatch transition

當天筆記摘錄
#

Problem 1 - LC 1143 Longest Common Subsequence
#

Pattern: 2D DP on two prefixes.

Why This Fits
#

At any pair of positions, the question is:

what is the LCS length for the prefixes up to these two positions?

That naturally gives a 2D table over:

prefix of text1
prefix of text2

Core State / Invariant
#

dp[i][j] = length of the longest common subsequence between text1[:i] and text2[:j]

Base Case
#

If either prefix is empty:

dp[i][0] = 0
dp[0][j] = 0

Reason:

an empty string has no common subsequence with positive length

Transition
#

If the new characters match:

text1[i - 1] == text2[j - 1]
=> dp[i][j] = dp[i - 1][j - 1] + 1

If they do not match:

dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

Why This Works
#

match:
- the matching characters can extend the best subsequence from the smaller prefixes
mismatch:
- one of the two last characters is not used, so drop one side and keep the better answer

Complexity
#

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

Can be compressed to:

Space: O(n)

Common Mistakes
#

using substring instead of subsequence reasoning
mixing character index with prefix length index
forgetting that mismatch takes max(up, left)
saying diagonal is used on every step

Strong Spoken Explanation
#

I define dp[i][j] as the LCS length between the prefixes text1[:i] and text2[:j]. The base row and base column are zero because an empty prefix cannot contribute any positive common subsequence. If the current characters match, I extend the smaller-prefix answer from the diagonal by one. If they do not match, I drop one side and keep the better result from up or left. The final answer is dp[m][n].

正確解法
#

上面的筆記保留了推理脈絡和當天需要修正的點。下面是我會提交的版本。

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
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

        return dp[m][n]