LC583
两个字符串的删除操作
二维 DP · 删除操作可视化:动态规划表word1=sea,word2=eat 最少删除步数使相同。
时间 O(n)空间 O(1)
题目1 / 15
题目与输入建立输入、目标与算法心智
插入/删除/替换
正在加载算法场景...
当前发生了什么
word1=sea,word2=eat 最少删除步数使相同。
机器状态
dp[i][j] LCS/删除数。
为什么正确
LCS 变种:n+m-2*LCS;或删到相等编辑距离。
不变量
最终相同⇔保留 LCS,删其余。
面试怎么说
LCS dp 或删除 dp O(mn)。
人类输入
word1=sea,word2=eat 最少删除步数使相同。
机制
LCS 变种:n+m-2*LCS;或删到相等编辑距离。
机器状态
dp[i][j] LCS/删除数。
可观察结果
最少删除 2 步。
不变量
- · 最终相同⇔保留 LCS,删其余。
常见误区
- · 与编辑距离相关但只允许删。
迁移练习
- · LC72 编辑距离
- · LC1143 LCS
面试怎么答
LCS dp 或删除 dp O(mn)。