交互式Python实验室

Longest Common Subsequence

Playground在加载时自动运行。点击运行我的代码来追踪你的Python代码 — 每一步实时动画展示。

解释·逐行

回放·逐步

挑战·引导式提示

XP·...

数据流水线

mastery 路径

Dijkstra's Shortest Path

0/1 Knapsack DP

Longest Common Subsequence

Coin Change DP

Topological Sort (Kahn's)

Kruskal's MST

Trie (Prefix Tree)

Floyd-Warshall All-Pairs Shortest Path

Segment Tree for Range Queries

Bit Manipulation Tricks

解释

Line 1

lcs('ABCBDAB', 'BDCAB') called. m=7, n=5.

为什么用这种方法？

We want the longest subsequence present in both strings. A subsequence doesn't need to be contiguous. BDAB is common with length 4.

Structured Explanation

Overview

最长公共子序列(LCS): 返回两个字符串的最长公共子序列的长度。

Analogy

就像比较两个日程找到共同的空闲时间。

Step-by-step

dp[i][j]=s1前i字符和s2前j字符的LCS长
s1[i-1]==s2[j-1]则dp[i][j]=dp[i-1][j-1]+1
否则dp[i][j]=max(dp[i-1][j],dp[i][j-1])
dp[m][n]是答案

Visual

s1="ABCBDAB" s2="BDCAB" dp[m][n]=4 → LCS="BCAB"

Common mistakes

[
"
以
为
不
重
建
就
能
返
回
L
C
S
字
符
串
"
,
"
索
引
偏
移
(
d
p
[
i
]
对
应
s
[
i
-
1
]
)
"
]

Practice questions

不只求长度，还要重建LCS字符串
改为最长公共子串(连续)

Time

O(mn)

Space

O(mn)，优化后O(min(m,n))

复杂度

时间

O(m × n)

空间

O(m × n)

复杂度概览

O(1)

O(log n)

O(n)

O(n log n)

O(n²)

n = 8范围 1-20

当 N = 8 时

复杂度	操作
O(1)	1
O(log n)	3
O(n)	8
O(n log n)	24
O(n²)	64

挑战

找出'ABCBDAB'和'BDCAB'的LCS。构建DP矩阵并追溯序列。

提示

字符匹配时dp[i][j]=dp[i-1][j-1]+1，否则max(dp[i-1][j], dp[i][j-1])。

代码工作室

Longest Common Subsequence

Monaco就绪

Python就绪

lesson.pyline 1

Loading editor...

输出控制台

1 lines

❯ 4

现实世界应用

1

The engine underneath `git diff`

2

DNA / Genomic sequencing

3

Levenshtein autocorrect bases

Comments

Loading comments...