以下是 LeetCode 3579. 字符串转换需要的最小操作数 的 Python3 实现基于 划分型动态规划 贪心匹配 的思路。核心思路1. 划分型 DPf[i] 表示将 word1[0:i] 转换为 word2[0:i] 所需的最小操作数。枚举最后一个子串的起始位置 j状态转移为f[i] min(f[j] cost(j, i-1)) 对于所有 j i2. 子串转换代价 calc(l, r, rev)计算将 word1[l:r1] 转换为 word2[l:r1] 的最小操作数。- revFalse不反转直接匹配- revTrue先花 1 次操作反转再匹配- 每个子串可以选择反转或不反转取最小值3. 贪心匹配calc 函数对于子串中的每个位置如果 word1[j] ! word2[i]- 若之前存在反向不匹配对 (b, a)即某个位置 word1 有 b 而 word2 需要 a则这两个位置可以通过一次交换同时解决操作数不变- 否则记录当前不匹配对 (a, b)需要一次替换操作这本质上是在统计不匹配字符对的数量能配对交换的就配对不能配对的用替换。Python3 代码pythonfrom typing import Listfrom collections import Counterfrom math import infclass Solution:def minOperations(self, word1: str, word2: str) - int:划分型动态规划 贪心匹配f[i] 将 word1[0:i] 转换为 word2[0:i] 的最小操作数def calc(l: int, r: int, rev: bool) - int:计算将 word1[l:r1] 转换为 word2[l:r1] 的最小操作数rev: 是否先反转 word1 的这段子串反转本身花费 1 次操作核心思想用 Counter 记录未匹配的不匹配对- 若遇到 (a,b) 且之前有未匹配的 (b,a)则两者可以交换不增加操作数- 否则需要一次替换操作cnt Counter() # 记录未匹配的不匹配对 (word1字符, word2字符)res 0 # 该子串所需的操作数for i in range(l, r 1):# 根据是否反转确定 word1 中对应的下标j r - (i - l) if rev else ia, b word1[j], word2[i]if a ! b:# 检查是否存在反向的未匹配对 (b, a)if cnt[(b, a)] 0:cnt[(b, a)] - 1 # 配对成功可以用一次交换解决else:cnt[(a, b)] 1 # 记录未匹配对需要一次替换res 1return resn len(word1)# f[i] 表示前缀 [0, i) 转换完成的最小操作数f [inf] * (n 1)f[0] 0 # 空串不需要操作for i in range(1, n 1):for j in range(i):# 子串 word1[j:i] 转换的代价# 选择不反转 或 先反转再转换反转花费1次操作cost_no_rev calc(j, i - 1, False)cost_with_rev 1 calc(j, i - 1, True)segment_cost min(cost_no_rev, cost_with_rev)f[i] min(f[i], f[j] segment_cost)return f[n]复杂度分析项目 复杂度时间 O(n^3) — 外层 DP O(n^2)每次 calc O(n)空间 O(n \|\Sigma\|^2) — DP 数组 O(n)Counter 最多 26 \times 26 个键其中 n \le 100O(n^3) 10^6 完全可接受。示例验证以示例 1 为例word1 abcdf, word2 dacbe- 最优划分ab | c | df- ab → 反转得 ba再替换 b→d 2 次操作- c → 无需操作 0 次- df → 替换 d→b再替换 f→e 2 次- 总计2 0 2 4 ✓该解法参考了 Doocs LeetCode 题解中的标准实现 。
