Kimi LeetCode 3579. 字符串转换需要的最小操作数 C++实现

这是 LeetCode 3579困难的 C 实现。核心思路是 划分型 DP 贪心匹配。核心思路1. 划分型 DPf[i] 表示将 word1[0..i-1] 转换为 word2[0..i-1] 的最小操作数。枚举最后一个子串的起始位置 j状态转移为f[i] min(f[i], f[j] cost(j, i-1))2. 子串内部的最小操作数贪心对于一个子串每个字符在每种操作中最多参与一次。关键观察- 如果存在一对位置 (i, j) 满足 word1[i]a, word2[i]b 且 word1[j]b, word2[j]a则可以用 1 次交换 同时解决这两个不匹配比各自替换2 次更优。- 无法配对的剩余字符只能逐个替换。- 子串还可以选择 先反转花费 1 次操作再按上述方式处理。3. calc 函数用 cnt[26][26] 记录未匹配的不匹配对 (a, b)。遍历子串时若当前不匹配 (a, b)检查是否存在之前的 (b, a) 可以配对交换否则记录为新的未匹配对。时间复杂度 O(n^3)空间复杂度 O(n)其中 n \le 100。C 代码cppclass Solution {public:int minOperations(string word1, string word2) {int n word1.length();vectorint f(n 1, INT_MAX);f[0] 0;for (int i 1; i n; i) {for (int j 0; j i; j) {// 不反转子串 [j, i-1]int a calc(word1, word2, j, i - 1, false);// 反转子串 [j, i-1]额外花费 1 次操作int b 1 calc(word1, word2, j, i - 1, true);int t min(a, b);f[i] min(f[i], f[j] t);}}return f[n];}private:// 计算将 word1[l..r]或反转后转换为 word2[l..r] 的最小操作数int calc(const string word1, const string word2, int l, int r, bool rev) {int cnt[26][26] {0}; // cnt[a][b] 表示未匹配的对 (a-b) 的数量int res 0;for (int i l; i r; i) {// revtrue 时word1 从右往左对应 word2 从左往右int j rev ? r - (i - l) : i;int a word1[j] - a;int b word2[i] - a;if (a ! b) {// 如果之前有 (b, a) 的未匹配对可以配对交换if (cnt[b][a] 0) {cnt[b][a]--;} else {// 否则记录为新的未匹配对需要一次替换cnt[a][b];res;}}}return res;}};关键解释- cnt[b][a] 0表示之前遇到过 word1 有 b 而 word2 期望 a 的位置。当前位置是 word1 有 a 而 word2 期望 b两者恰好可以 一次交换 解决因此抵消之前的记录不增加操作数。- 反转操作revtrue 时子串 word1[l..r] 被当作反转后的顺序与 word2[l..r] 比较额外加 1 是因为反转本身算一次操作。- DP 转移对每个位置 i枚举所有可能的前一个分割点 j取最小值。