LeetCode 583 Delete Operation for Two Strings 题解：基于 O(n²) 动态规划的最小删除步数（Go 实现）

LeetCode 583 Delete Operation for Two Strings 题解：基于 O(n²) 动态规划的最小删除步数（Go 实现）

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

导读

LeetCode 583「Delete Operation for Two Strings」要求通过删除字符使两个字符串相等，并统计最少删除次数。这是一道典型的双序列（two-sequence）动态规划题，与最长公共子序列（LCS）问题同源，也是编辑距离（Edit Distance）的简化变体。本文以 leetcode/0583.Delete-Operation-for-Two-Strings/README.md 的官方题解为主线，结合仓库中 Go 实现源码 与 测试用例，从状态定义、转移方程推导到滚动数组优化，完整讲解该题的求解过程，并给出可直接运行、通过全量测试用例的 Go 代码。

题目描述

给定两个字符串word1和word2，返回使word1与word2相同所需的最小步数（minimum number of steps）。

每一步可以只删除两个字符串中的任意一个字符（in one step, you can delete exactly one character in either string），也就是说操作只有「删除」这一种，且每次只能删一个字符。

示例 1：

Input: word1 = "sea", word2 = "eat" Output: 2 Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".

即：先删掉"sea"中的s得到"ea"，再删掉"eat"中的t得到"ea"，共 2 步。

示例 2：

Input: word1 = "leetcode", word2 = "etco" Output: 4

约束条件：

• 1 <= word1.length, word2.length <= 500
• word1和word2仅由小写英文字母组成（consist of only lowercase English letters）

题目大意

给定两个单词word1和word2，找到使得word1和word2相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。

解题思路

为什么是 O(n²) 动态规划

从题目数据量级判断：word1.length与word2.length最大均为 500，二者相乘达到 250,000。若使用指数级搜索或递归枚举所有删除方案必然超时，因此此题一定是O(n²) 动态规划题。双序列 DP 的经典套路是以两个字符串的前缀为维度定义状态，逐格填表求解。

状态定义

定义dp[i][j]表示word1[:i]与word2[:j]匹配（变为相同字符串）所删除的最少步数，其中word1[:i]表示word1的前i个字符（不含word1[i]），word2[:j]同理。

边界条件：

• dp[i][0] = i：word2为空串时，只能把word1前i个字符全部删掉，共删除i次；
• dp[0][j] = j：word1为空串时，只能把word2前j个字符全部删掉，共删除j次。

状态转移方程推导

考察word1[i-1]与word2[j-1]（下标从 0 计数时，前缀word1[:i]的最后一个字符是word1[i-1]）：

• 若word1[i-1] == word2[j-1]：最后一个字符相同，无需删除它们，问题退化为「word1[:i-1]与word2[:j-1]匹配所需的最少删除步数」，即

  dp[i][j] = dp[i-1][j-1]

• 若word1[i-1] != word2[j-1]：最后一个字符不相同，二者不可能同时保留，必须删掉其中一个，因此需要考虑两种情况：

  • 删除word1[i-1]，即问题退化为「word1[:i-1]与word2[:j]匹配」，步数为1 + dp[i-1][j]；
  • 删除word2[j-1]，即问题退化为「word1[:i]与word2[:j-1]匹配」，步数为1 + dp[i][j-1]；
  • 取二者较小值，即

  dp[i][j] = 1 + min(dp[i][j-1], dp[i-1][j])

综上，动态转移方程为：

dp[i][j] = dp[i-1][j-1] , word1[i-1] == word2[j-1] dp[i][j] = 1 + min(dp[i][j-1], dp[i-1][j]) , word1[i-1] != word2[j-1]

最终答案存储在dp[len(word1)][len(word2)]中。

与最长公共子序列（LCS）的关系

从转移方程可以看出，当word1[i-1] == word2[j-1]时直接继承dp[i-1][j-1]，这与 1143. Longest Common Subsequence 的求法高度对称：LCS 在字符相等时加一，不等时取max(dp[i][j-1], dp[i-1][j])（可参考仓库中 1143 的 Go 实现）。

事实上本题存在一个等价的简洁结论：最终保留的相同字符串必然是word1与word2的最长公共子序列，因此最小删除步数也等于：

len(word1) + len(word2) - 2 * len(LCS(word1, word2))

这与 DP 方程推得的结果完全一致，可作为验证答案正确性的一种手段。

代码实现

以下为仓库 583. Delete Operation for Two Strings.go 中的完整实现，与 README 题解代码一致：

package leetcode func minDistance(word1 string, word2 string) int { dp := make([][]int, len(word1)+1) for i := 0; i < len(word1)+1; i++ { dp[i] = make([]int, len(word2)+1) } for i := 0; i < len(word1)+1; i++ { dp[i][0] = i } for i := 0; i < len(word2)+1; i++ { dp[0][i] = i } for i := 1; i < len(word1)+1; i++ { for j := 1; j < len(word2)+1; j++ { if word1[i-1] == word2[j-1] { dp[i][j] = dp[i-1][j-1] } else { dp[i][j] = 1 + min(dp[i][j-1], dp[i-1][j]) } } } return dp[len(word1)][len(word2)] } func min(x, y int) int { if x < y { return x } return y }

代码要点说明

1. 二维 DP 表的初始化：dp的维度为(len(word1)+1) × (len(word2)+1)，多出的一行一列用于表示空串前缀，便于统一处理边界。
2. 首行首列赋初值：dp[i][0] = i与dp[0][j] = j对应「把一侧字符串全部删空」的语义，是转移方程正确性的地基。
3. 填表顺序：两层循环从左到右、从上到下进行，因为dp[i][j]只依赖dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]三个已经算好的前置状态。
4. min辅助函数：仓库中按包内私有函数形式定义（小写），与leetcode包其他题解风格一致，不会污染外部 API。

测试用例验证

仓库为本题配套了 583. Delete Operation for Two Strings_test.go，采用表驱动（table-driven）方式组织用例，覆盖题目给出的两个示例：

qs := []question583{ { para583{"sea", "eat"}, ans583{2}, }, { para583{"leetcode", "etco"}, ans583{4}, }, }

其中para583封装输入参数word1、word2，ans583封装期望输出one；测试函数Test_Problem583遍历用例，调用minDistance(p.word1, p.word2)并打印输入输出。该题解在仓库中实现了 100% 测试覆盖的目标，读者可在本地 Go 环境（Go 1.x，见仓库根目录 go.mod）下通过以下方式运行验证：

go test ./leetcode/0583.Delete-Operation-for-Two-Strings/ -v

复杂度分析

• 时间复杂度：O(n × m)，其中n = len(word1)，m = len(word2)。两层嵌套循环各遍历一次，每个状态的计算为 O(1)。
• 空间复杂度：O(n × m)，需要存储完整二维 DP 表。在n = m = 500的约束下，表规模为 501 × 501，内存开销完全可控。

空间优化：滚动数组

观察转移方程可以发现，dp[i][j]只依赖当前行j-1列以及上一行j-1、j列的状态，因此可以只用两行（或一维数组加两个临时变量）滚动计算，将空间复杂度降至O(m)。需要注意的是，若退化为单行数组，dp[i-1][j-1]的旧值需要先用临时变量保存，避免被覆盖。

总结

• 本题核心是双序列 DP：状态dp[i][j]表示两个前缀变为相同串的最小删除步数；
• 转移分两类：末字符相等直接继承，不等则删除其一取较小值；
• 边界（空串情况）是初始化的关键；
• 时间复杂度 O(n²)、空间复杂度 O(n²)，可用滚动数组优化至 O(m)；
• 题目与 LCS、编辑距离系列题目同源，理解其一即可触类旁通。

通过阅读 README 题解 并结合 源码实现 与 测试用例，读者可以完整复现该题的求解链路，并将这套「前缀 + 双序列 DP」的模板迁移到更多字符串编辑类问题中。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go