目录一、题目描述输入格式:输出格式:输入样例:输出样例:二、解题思路一先明确问题本质是「最小编辑距离」1. 操作拆解与编辑距离的对应2. 样例验证二基础思路二维动态规划DP1. 状态定义2. 初始化边界条件3. 核心状态转移方程4. 最终结果三关键优化一维滚动数组滚动数组的核心逻辑四代码逐行解析结合 DP 逻辑五核心要点总结三、Python代码四、总结一、题目描述给出两个字符串 s,t你可以进行两种操作删除其中一个字符串的一个位置的字符改变一个字符串的一个位置的字符为任意的字符。问最少几次操作能使这两个字符串相同。输入格式:输入两行英文小写字符串 s 与 t (1≤∣s∣,∣t∣≤10000)。输出格式:输出一个整数代表最少几次操作可以使得这两个字符串相同。输入样例:xxcdsghwydsg输出样例:3二、解题思路一先明确问题本质是「最小编辑距离」1. 操作拆解与编辑距离的对应题目允许 2 种操作但实际可拆解为3 种核心有效操作每种操作代价均为 1这正是经典编辑距离的标准操作操作 1删除 s 的一个字符 → 对应编辑距离的「删除」操作将 s 转 t删去 s 的一个字符操作 2删除 t 的一个字符 → 对应编辑距离的「插入」操作给 s 插入一个字符等价于删 t 的字符最终让两字符串相同操作 3修改一个字符为任意字符 → 对应编辑距离的「替换」操作让 s 和 t 对应位置的字符一致。问题目标让两个字符串相同的最少操作数 将 s 转换为 t 的最小编辑距离或 t 转 s代价相同。2. 样例验证输入样例sxxcdsg、thwydsg长度均为 6字符逐位对比x≠h、x≠w、c≠y、dd、ss、gg前 3 位字符不同直接修改 3 次即可让两字符串相同总操作数 3与样例输出一致这正是编辑距离的直观体现。二基础思路二维动态规划DP代码是空间优化后的一维 DP但理解一维的前提是先掌握原始二维 DP核心是状态定义和转移方程这是解题的根本。1. 状态定义定义二维数组dp[i][j]将s 的前 i 个字符转换为t 的前 j 个字符所需的最少操作数。注字符串索引从 0 开始所以 s 的前 i 个字符是s[0..i-1]t 的前 j 个字符是t[0..j-1]2. 初始化边界条件dp[i][0] is 的前 i 个字符转成空字符串t 的前 0 个字符只需删除 s 的 i 个字符代价 idp[0][j] j空字符串转成 t 的前 j 个字符只需插入 j 个字符等价于删除 t 的 0 个、给 s 插 j 个代价 j。3. 核心状态转移方程遍历 s 的每个字符i 从 1 到 m、t 的每个字符j 从 1 到 n分两种情况情况 1s [i-1] t [j-1]对应位置字符相同无需任何操作最少操作数继承「s 前 i-1 个转 t 前 j-1 个」的结果即dp[i][j]dp[i−1][j−1]情况 2s [i-1] ! t [j-1]对应位置字符不同需从 3 种操作中选代价最小的一种加 1 次操作代价即dp[i][j]min(dp[i−1][j],dp[i][j−1],dp[i−1][j−1])1其中dp[i-1][j] 1删除 s 的第 i 个字符再将 s 前 i-1 个转 t 前 j 个dp[i][j-1] 1删除 t 的第 j 个字符再将 s 前 i 个转 t 前 j-1 个dp[i-1][j-1] 1修改 s 的第 i 个字符为 t 的第 j 个再将 s 前 i-1 个转 t 前 j-1 个。4. 最终结果dp[m][n]m 是 s 长度n 是 t 长度即 s 全部字符转 t 全部字符的最少操作数。三关键优化一维滚动数组题目中字符串长度最大为 10000若用二维 DP 数组大小为10000*100001e8假设内存限制为1024 MB则会超出。观察状态转移方程发现dp [i][j] 的计算仅依赖上一行的 3 个值dp [i-1][j]、dp [i][j-1]、dp [i-1][j-1]无需保存整个二维数组只需用一维数组保存「上一行的状态」遍历过程中逐步更新为「当前行的状态」将空间复杂度从O(mn)降至O(min(m,n))最优。滚动数组的核心逻辑用一维数组dp[j]替代二维数组初始时 dp [j] dp [0][j]即 s 前 0 个字符转 t 前 j 个字符的操作数遍历 s 的每个字符i 从 1 到 m逐行更新 dp 数组dp[0]会被更新为dp[i][0] is 前 i 个字符转空的操作数遍历 t 的每个字符j 从 1 到 n时dp [j] 旧值是上一行的dp[i-1][j]dp [j-1] 新值是当前行的dp[i][j-1]上一行的 dp [i-1][j-1]会被覆盖因此需要提前保存这个值代码中的prev_prev遍历结束后dp[n]即为最终结果等价于二维的dp[m][n]。四代码逐行解析结合 DP 逻辑先明确变量定义m len(s)n len(t)代码先确保n是较短字符串长度让一维数组更小优化空间。s input().strip() t input().strip() m, n len(s), len(t) # 确保n是较短字符串的长度优化滚动数组空间一维数组长度为n1越小越好 if m n: s, t t, s m, n n, m交换 s 和 t让t是较短的字符串一维 dp 数组的长度为n1最大化节省空间比如 s 长 10000t 长 100dp 数组仅 101 个元素。# 初始化dp数组dp[j]表示s前0个字符与t前j个字符的最少操作次数即二维DP的dp[0][j] j dp list(range(n 1))初始化一维 dp 数组对应二维 DP 的第 0 行dp[0]0, dp[1]1, dp[2]2, ..., dp[n]n符合边界条件dp[0][j]j。for i in range(1, m 1): prev_prev dp[0] # 保存上一轮的dp[0]即二维DP的dp[i-1][0]s前i-1个转t前0个的操作数 dp[0] i # 更新当前轮的dp[0]即二维DP的dp[i][0] is前i个转t前0个的操作数外层循环遍历 s 的前 i 个字符i 从 1 到 m对应二维 DP 的第 i 行prev_prev核心缓存变量保存上一行前一列的 dp 值即二维的dp[i-1][j-1]因为一维数组更新时这个值会被覆盖必须提前保存每次循环先更新dp[0]为i符合边界条件dp[i][0] i。for j in range(1, n 1): current dp[j] # 保存当前dp[j]的旧值作为下一轮j1的prev_prev即下一个dp[i-1][j] # 若字符相同无需操作dp[j] 上一行前一列的dp值prev_prev dp[i-1][j-1] if s[i-1] t[j-1]: dp[j] prev_prev # 若字符不同取三种操作的最小值1对应二维DP的转移方程 else: dp[j] min(dp[j], dp[j-1], prev_prev) 1 prev_prev current # 更新prev_prev为当前dp[j]的旧值供下一个j使用内层循环遍历 t 的前 j 个字符j 从 1 到 n对应二维 DP 的第 j 列current保存当前dp[j]的旧值即上一行的dp[i-1][j]因为下一个 j 循环需要这个值作为prev_prev即dp[i-1][j]字符相同时dp[j] prev_prev→ 等价于二维的dp[i][j] dp[i-1][j-1]字符不同时min(dp[j], dp[j-1], prev_prev) 1→ 对应二维的转移方程dp[j]旧值即上一行的dp[i-1][j]删 sdp[j-1]新值即当前行的dp[i][j-1]删 tprev_prev上一行的dp[i-1][j-1]修改每次循环结束更新prev_prev为current供下一个 j 使用即下一列的dp[i-1][j-1]。print(dp[n])最终dp[n]是一维数组的最后一个元素等价于二维 DP 的dp[m][n]即 s 全部字符转 t 全部字符的最少操作数。五核心要点总结问题转化题目要求的最少操作数 两字符串的最小编辑距离操作删 s、删 t、修改与编辑距离删除、插入、替换一一对应DP 核心二维 DP 的状态定义dp[i][j]s 前 i 转 t 前 j 的最少操作数和转移方程是解题基础字符相同继承上一状态不同则取三种操作的最小值 1空间优化利用 DP 转移的行依赖性将二维数组降为一维滚动数组空间复杂度从O(mn)降至O(min(m,n))适配 10000 长度的字符串缓存关键值一维数组更新时dp[i-1][j-1]会被覆盖因此需要prev_prev提前保存这是滚动数组实现的关键细节。该思路的时间复杂度为O(mn)必须遍历两个字符串的所有字符空间复杂度为O(min(m,n))是该问题的最优解法能高效处理题目中 10000 长度的输入限制。三、Python代码s input().strip() t input().strip() m, n len(s), len(t) # 确保n是较短字符串的长度优化滚动数组空间 if m n: s, t t, s m, n n, m # 初始化dp数组dp[j]表示s前0个字符与t前j个字符的最少操作次数 dp list(range(n 1)) for i in range(1, m 1): prev_prev dp[0] # 保存上一轮的dp[0]即s前i-1个字符与t前0个字符的操作次数 dp[0] i # 更新当前轮的dp[0]s前i个字符与t前0个字符的操作次数 for j in range(1, n 1): current dp[j] # 保存当前dp[j]作为下一轮的prev_prev # 若字符相同无需操作代价等于上一轮的dp[j-1] if s[i-1] t[j-1]: dp[j] prev_prev # 否则取“删s、删t、修改”的最小代价1 else: dp[j] min(dp[j], dp[j-1], prev_prev) 1 prev_prev current # 更新prev_prev为当前轮的dp[j]旧值 print(dp[n])四、总结本文介绍了如何计算两个字符串的最小编辑距离使其通过最少操作删除或修改字符变为相同字符串。解题采用动态规划方法通过二维DP状态转移方程字符相同继承前状态不同取三种操作最小值1实现并优化为一维滚动数组以节省空间。最终时间复杂度O(mn)空间复杂度O(min(m,n))适用于大字符串处理。Python代码演示了该算法的具体实现。