What is the best approach for solving Longest Common Subsequence?

State transition dynamic programming is optimal, using a DP table where DP[i][j] tracks the LCS length of prefixes of both strings.

Can LCS be solved recursively without DP?

Yes, but naive recursion has exponential time complexity; memoization or DP is needed for strings up to length 1000.

How do I optimize space in LCS DP solutions?

You can keep only two rows of the DP table at a time, updating iteratively to reduce space from O(m*n) to O(n).

Does LCS require contiguous characters?

No, LCS allows characters to be non-contiguous while maintaining relative order, which differentiates it from substring problems.

What common mistakes occur in LCS problems?

Confusing subsequences with substrings, missing base cases, and attempting recursion without memoization are frequent errors.

#1143

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

最长公共子序列

给定两个字符串 text1 和 text2 ，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0 。一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。例如， "ace" 是 …

字符串动态规划

题目描述

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。

示例 2：

输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。

示例 3：

输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 。

提示：

1 <= text1.length, text2.length <= 1000
text1 和 text2 仅由小写英文字符组成。

lightbulb

解题思路

方法一：动态规划

我们定义 $f[i][j]$ 表示 $text1$ 的前 $i$ 个字符和 $text2$ 的前 $j$ 个字符的最长公共子序列的长度。那么答案为 $f[m][n]$ ，其中 $m$ 和 $n$ 分别为 $text1$ 和 $text2$ 的长度。

如果 $text1$ 的第 $i$ 个字符和 $text2$ 的第 $j$ 个字符相同，则 $f[i][j] = f[i - 1][j - 1] + 1$ ；如果 $text1$ 的第 $i$ 个字符和 $text2$ 的第 $j$ 个字符不同，则 $f[i][j] = max(f[i - 1][j], f[i][j - 1])$ 。即状态转移方程为：

f[i][j] = \begin{cases} f[i - 1][j - 1] + 1, & text1[i - 1] = text2[j - 1] \\ \max(f[i - 1][j], f[i][j - 1]), & text1[i - 1] \neq text2[j - 1] \end{cases}

时间复杂度 $O(m \times n)$ ，空间复杂度 $O(m \times n)$ 。其中 $m$ 和 $n$ 分别为 $text1$ 和 $text2$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        f = [[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]:
                    f[i][j] = f[i - 1][j - 1] + 1
                else:
                    f[i][j] = max(f[i - 1][j], f[i][j - 1])
        return f[m][n]

speed

复杂度分析

指标	值
时间	complexity is O(m _n) because each DP cell is computed once, where m and n are the lengths of text1 and text2. Space complexity is O(m_ n) for the full table, but can be reduced to O(n) using two-row optimization.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate recognizes DP[i][j] as the key state representation for subsequence lengths.
question_mark
They correctly identify state transitions for character matches versus mismatches.
question_mark
They optimize space with rolling rows to reduce memory without affecting correctness.

warning

常见陷阱

外企场景

error
Confusing subsequence with substring, leading to incorrect DP updates.
error
Forgetting to initialize DP table edges, causing index errors or wrong LCS length.
error
Using recursive solutions without memoization, leading to exponential time complexity.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return the actual longest common subsequence string instead of just its length.
arrow_right_alt
Compute LCS for more than two strings using multidimensional DP.
arrow_right_alt
Apply the pattern to sequences of numbers or other comparable items instead of characters.

help

常见问题

外企场景

继续练习

#1147 段式回文 #1092 最短公共超序列 #1048 最长字符串链