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也就是说操作只有「删除」这一种且每次只能删一个字符。示例 1Input: 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 步。示例 2Input: word1 leetcode, word2 etco Output: 4约束条件1 word1.length, word2.length 500word1和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] iword2为空串时只能把word1前i个字符全部删掉共删除i次dp[0][j] jword1为空串时只能把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 }代码要点说明二维 DP 表的初始化dp的维度为(len(word1)1) × (len(word2)1)多出的一行一列用于表示空串前缀便于统一处理边界。首行首列赋初值dp[i][0] i与dp[0][j] j对应「把一侧字符串全部删空」的语义是转移方程正确性的地基。填表顺序两层循环从左到右、从上到下进行因为dp[i][j]只依赖dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]三个已经算好的前置状态。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、word2ans583封装期望输出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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考