“最小删除步数”错题复盘

在刷“最小删除步数使两个字符串相等”这道题时，我从“思路跑偏”到“实现全错”，再到“逐步修正”，踩了很多典型坑。这道题看似是简单的字符串操作，实则考察对动态规划（LCS）的理解和题目本质的拆解能力，非常适合用来复盘总结。本文结合我的解题过程，梳理思维漏洞、提炼编程意识、巩固核心知识点，帮自己和同类学习者少走弯路。

一、题目回顾

给定两个字符串 word1 和 word2，返回使它们相等所需的最少删除步数。删除一个字符的步数为1，要求通过删除操作让两个字符串最终完全一致。

示例：
输入：word1 = "sea"，word2 = "eat"
输出：2
解释：删除 sea 中的 s（1步），删除 eat 中的 t（1步），最终都得到 ea，总步数2。

二、我的解题翻车历程

初始思路：误以为“最小步数 = max(len(word1), len(word2)) - 最长公共子序列（LCS）长度”，导致示例计算结果为1（实际应为2）；
DP实现错误：LCS的状态定义、边界初始化、转移方程、循环范围全错，比如把dp[i][j]定义为“word1[i]结尾和word2[j]结尾的公共子序列长度”，漏了不匹配场景的处理；
逐步修正：先纠正核心公式，再重构LCS的DP实现，最终才得到正确结果。

三、核心复盘：

（一）思维漏洞：看不见的“解题绊脚石”

思维漏洞是解题的根源错误，比代码语法错误更隐蔽，也更难发现。

漏洞1：误解题目本质，把“双字符串删除”当成“单字符串删除”

我的初始思路错把“两个字符串都需删除非公共部分”当成“最长字符串删除非公共部分即可”，核心原因是没拆解清楚“使两个字符串相等”的本质：

正确逻辑：要让两个字符串相等，最优选择是保留它们的“最长公共子序列（LCS）”——LCS是两者共有的最长部分，保留它需要删除的字符最少；
错误逻辑：误以为“让短字符串变成长字符串的子序列”，忽略了“长字符串也需要删除非公共部分”；
反例验证：word1="sea"（3个字符）、word2="eat"（3个字符），LCS长度2，按错误思路计算为3-2=1，但实际需要删除2次（两个字符串各删1次），直接暴露逻辑漏洞。

漏洞2：对DP状态定义模糊，导致实现“全盘皆错”

动态规划的核心是“状态定义”，但我一开始对LCS的状态定义完全跑偏：

错误定义：dp[i][j]表示“word1[i]结尾和word2[j]结尾的公共子序列最大长度”；
问题所在：没包含“前i个字符”的范围（忽略空字符串前缀），也没明确“公共子序列是全局最长”，导致后续转移方程和循环范围全跟着错；
连锁反应：因为定义错，我没设置第0行第0列（空字符串前缀的LCS长度为0），循环从i=1、j=1开始，直接漏掉了word1[0]和word2[0]的匹配处理。

漏洞3：忽略“状态转移的完整性”，只考虑匹配场景

LCS的转移方程包含“匹配”和“不匹配”两种情况，但我只写了匹配时的逻辑：

错误实现：仅当word1[i] == word2[j]时，dp[i][j] += dp[i-1][j-1]；
问题所在：不匹配时没有继承“上一轮的最长长度”，导致DP数组无法积累有效数据，最终LCS长度计算为0；
本质原因：对“子序列不要求连续”的理解不透彻——不匹配时，最长公共子序列要么来自word1的前i-1个字符，要么来自word2的前j-1个字符，必须二选一取最大值。

（二）必须建立的编程意识

思维漏洞的背后是编程意识的缺失，建立以下意识能从根源上减少错误。

意识1：“题目本质拆解”意识——先搞懂“要做什么”，再想“怎么做”

拿到题目不要急于写代码，先拆解本质：

本题本质：“两个字符串删除非公共部分，保留最长公共子序列”，所以步数=word1需删次数+word2需删次数；
推导过程：word1需删次数=len(word1)-LCS长度，word2需删次数=len(word2)-LCS长度，总步数=len(word1)+len(word2)-2*LCS长度；
如何培养：遇到字符串“相等”“匹配”“最长”类问题，先问自己“核心是找什么共性/差异”，再关联已知算法（如LCS、动态规划）。

意识2：“状态定义先行”意识——DP的灵魂是“定义”，不是“转移”

动态规划的所有操作（初始化、转移方程、循环）都必须围绕“状态定义”展开：

正确示范（LCS状态定义）：dp[i][j]表示“word1的前i个字符（word1[0..i-1]）和word2的前j个字符（word2[0..j-1]）的最长公共子序列长度”；
定义要点：明确“范围”（前i个/前j个）、明确“含义”（最长公共子序列长度）、包含“边界场景”（i=0或j=0时为空字符串）；
如何培养：写DP代码前，先在注释里写清dp[i][j]的定义，再思考“这个定义下，边界是什么？转移方程是什么？”。

意识3：“边界条件兜底”意识——不要忽略“极端场景”

边界条件是DP的“地基”，忽略边界会导致整个计算崩塌：

本题LCS的边界条件：
1. i=0（word1为空）：无论j是多少，LCS长度为0 → dp[0][j] = 0；
2. j=0（word2为空）：无论i是多少，LCS长度为0 → dp[i][0] = 0；
我的错误：没设置第0行第0列，直接从i=1、j=1开始循环，导致word1[0]和word2[0]的匹配无法被处理；
如何培养：定义完DP状态后，先思考“当其中一个维度为0时，结果是什么？”，并在代码中优先初始化边界。

意识4：“转移方程闭环”意识——覆盖所有场景，不遗漏分支

状态转移方程必须覆盖“所有可能的情况”，不能只考虑一部分：

本题LCS的转移方程（闭环示例）：
1. 匹配时（word1[i-1] == word2[j-1]）：dp[i][j] = dp[i-1][j-1] + 1（继承前i-1、j-1的结果，加当前匹配的1）；
2. 不匹配时（word1[i-1] != word2[j-1]）：dp[i][j] = max(dp[i-1][j], dp[i][j-1])（继承两种情况的最大值）；
我的错误：只写了匹配场景，且用了+=（应该是直接赋值），导致不匹配时DP值保持为0；
如何培养：写完转移方程后，问自己“有没有遗漏的场景？”“每种场景下的依赖关系是什么？”。

（三）必须记住的核心知识点

这道题的核心是LCS（最长公共子序列），以及基于LCS的题目公式，这两个知识点是高频考点，必须牢牢记住。

知识点1：LCS的动态规划实现（必背模板）

LCS是字符串类动态规划的“母题”，很多题目（如最长公共子串、编辑距离、本题）都基于它变形，其DP实现有固定模板：

状态定义：dp[i][j] = word1前i个字符和word2前j个字符的最长公共子序列长度；
边界初始化：dp[0][j] = 0（word1为空），dp[i][0] = 0（word2为空）；
转移方程：
- 匹配：dp[i][j] = dp[i-1][j-1] + 1；
- 不匹配：dp[i][j] = max(dp[i-1][j], dp[i][j-1])；
数组维度：(len(word1)+1) × (len(word2)+1)（多开一行一列处理空前缀）；
时间复杂度：O(n×m)（n、m为两个字符串长度），空间复杂度：O(n×m)（可优化为O(min(n,m))）。

知识点2：本题核心公式（基于LCS的衍生）

“最小删除步数使两个字符串相等”的公式是：
最小步数 = len(word1) + len(word2) - 2 × LCS长度

推导逻辑：两个字符串都要删除“非LCS部分”，word1删除次数=len(word1)-LCS长度，word2删除次数=len(word2)-LCS长度，总和即两者之和减2倍LCS长度；
记忆技巧：“总长度减两倍公共长度”，公共部分越长，删除步数越少，符合直觉。

四、修正后的最终代码

class Solution(object):def minDistance(self, word1, word2):""":type word1: str:type word2: str:rtype: int"""n1, n2 = len(word1), len(word2)# 状态定义：dp[i][j] = word1前i个字符和word2前j个字符的LCS长度dp = [[0]*(n2+1) for _ in range(n1+1)]# 填充DP表格（边界已初始化）for i in range(1, n1+1):for j in range(1, n2+1):if word1[i-1] == word2[j-1]:dp[i][j] = dp[i-1][j-1] + 1else:dp[i][j] = max(dp[i-1][j], dp[i][j-1])lcs_len = dp[n1][n2]# 核心公式：总长度 - 2*LCS长度return n1 + n2 - 2 * lcs_len