2025-11-26：字符串转换需要的最小操作数。用go语言，给定两个等长字符串 word1 和 word2，要求把 word1 变成 word2。

可以先把 word1 分成一个或多个连续片段（子串），然后对这些片段分别进行操作。允许的操作有三种：

• 在某个片段内，把某个位置上的字符改为另一个小写字母（替换）。

• 在片段内交换任意两个字符的位置（交换）。

• 将整个片段的字符顺序倒过来（反转）。

每进行一次上述任一操作都计为一次操作。

此外，每个片段中的任意字符下标最多只能被一次操作所涉及——也就是说，任何字符位置不能被多次用于替换、交换或反转。

子串指的是原字符串中的连续且非空的一段字符。

目标是用尽可能少的操作次数把 word1 变为 word2，返回所需的最小操作数。

1 <= word1.length == word2.length <= 100。

word1 和 word2 仅由小写英文字母组成。

输入： word1 = “abcdf”, word2 = “dacbe”。

输出： 4。

解释：

将 word1 分割为 “ab”、“c” 和 “df”。操作如下：

对于子串 “ab”：

执行类型 3 的操作：“ab” -> “ba”。

执行类型 1 的操作：“ba” -> “da”。

对于子串 “c”：无需操作。

对于子串 “df”：

执行类型 1 的操作：“df” -> “bf”。

执行类型 1 的操作：“bf” -> “be”。

题目来自力扣3579。

分步骤描述

1. 初始化与预处理反转操作成本（revOp 数组）

   • 目的：计算字符串中每个子串通过反转操作（操作类型3）转换为目标子串所需的最小操作数。反转操作允许交换字符位置，其成本取决于字符不匹配的程度。
   • 中心扩展法：代码遍历所有可能的子串中心（共 2n-1 个，包括字符位置和字符间位置）。对于每个中心点：
     • 设置左右指针 l 和 r，分别向左右扩展，形成子串区间 [l, r]。
     • 在扩展过程中，调用 update 函数处理字符对：
       • 比较 word1[l] 与 word2[r] 以及 word1[r] 与 word2[l]（当 l ≠ r 时），模拟反转操作下的字符映射。
       • update 函数维护一个字符对计数数组 cnt（大小 26×26）。如果字符对 (x, y) 存在相反方向的配对 (y, x)，则减少操作数（利用交换操作抵消成本）；否则增加操作数。
     • 将当前子串 [l, r] 的反转操作数记录到二维数组 revOp[l][r] 中。
   • 作用：预处理后，revOp[l][r] 表示子串 word1[l:r+1] 反转后匹配 word2[l:r+1] 的最小操作数。例如，子串 “ab” 反转后变为 “ba”，再通过替换操作匹配目标。

2. 动态规划填充 f 数组

   • 目的：计算将 word1 的前缀转换为 word2 前缀的最小操作数，支持字符串分割为连续片段。每个片段可选择直接处理或反转后处理。
   • 数组定义：f[i] 表示将 word1 的前 i 个字符转换为 word2 前 i 个字符的最小操作数（f[0] = 0 表示空前缀）。
   • 填充过程：
     • 遍历每个位置 i（从 0 到 n-1），计算 f[i+1]。
     • 对于每个 i，枚举所有可能的分割点 j（从 i 递减到 0），将子串 [j, i] 作为一个片段：
       • 重置 cnt 数组和操作计数器 op。
       • 不反转情况：顺序处理子串 [j, i]，调用 update 函数逐字符比较 word1[k] 和 word2[k]（k 从 j 到 i），计算通过替换和交换操作的成本 op。
       • 反转情况：直接使用预处理的 revOp[j][i] 作为该片段的反转操作成本。
       • 取两种情况的最小值：min(op, revOp[j][i])。
       • 更新 f[i+1] = min(f[i+1], f[j] + min_value)，即前 j 个字符的成本加上当前片段的成本。
   • 示例：对于输入 word1 = "abcdf", word2 = "dacbe"，分割为 "ab"、"c"、"df"：
     • 片段 "ab"：反转操作成本 revOp[0][1] = 2（先反转为 “ba”，再替换为 “da”）。
     • 片段 "c"：无需操作（字符匹配）。
     • 片段 "df"：直接操作成本 op = 2（两次替换）。
     • 总操作数 f[5] = f[2] + 2 + f[3] + 0 + f[5] + 2 = 4。

3. 结果提取

   • 动态规划完成后，f[n] 即为整个字符串转换的最小操作数。代码返回 f[n] 作为结果。

时间复杂度和空间复杂度

• 时间复杂度：

  • 预处理 revOp 数组使用中心扩展法，共有 O(n) 个中心，每个中心扩展最多 O(n) 次，每次扩展调用 O(1) 的 update 函数，因此预处理阶段复杂度为 O(n²)。
  • 动态规划阶段：外层循环遍历 n 个位置，内层循环对于每个 i 枚举 j 从 i 到 0，且每个 j 需要处理长度为 O(i-j) 的子串（通过 update 函数）。内层循环的总代价为 O(i²)，因此整体复杂度为 O(n³)（因为 ∑i² 从 0 到 n-1 是 O(n³)）。
  • 总时间复杂度：O(n³)，由于 n ≤ 100，实际计算可行。

• 额外空间复杂度：

  • revOp 数组大小为 n × n，占用 O(n²) 空间。
  • 动态规划数组 f 大小为 n+1，占用 O(n) 空间。
  • 字符对计数数组 cnt 大小为 26×26，为常数空间 O(1)。
  • 总空间复杂度：O(n²)，主要由 revOp 数组决定。

Go完整代码如下：

package main

import (
	"fmt"
	"math"
)

func minOperations(s, t string) int {
	var cnt [26][26]int
	var op int
	update := func(x, y byte) {
		if x == y {
			return
		}
		x -= 'a'
		y -= 'a'
		if cnt[y][x] > 0 {
			cnt[y][x]--
		} else {
			cnt[x][y]++
			op++
		}
	}

	n := len(s)
	// 预处理 revOp
	revOp := make([][]int, n)
	for i := range revOp {
		revOp[i] = make([]int, n)
	}
	// 中心扩展法
	// i 为偶数表示奇长度子串，i 为奇数表示偶长度子串
	for i := range 2*n - 1 {
		cnt = [26][26]int{}
		op = 1
		// 从闭区间 [l,r] 开始向左右扩展
		l, r := i/2, (i+1)/2
		for l >= 0 && r < n {
			update(s[l], t[r])
			if l != r {
				update(s[r], t[l])
			}
			revOp[l][r] = op
			l--
			r++
		}
	}

	f := make([]int, n+1)
	for i := range n {
		res := math.MaxInt
		cnt = [26][26]int{}
		op = 0 // 不反转时的最小操作次数
		for j := i; j >= 0; j-- {
			update(s[j], t[j])
			res = min(res, f[j]+min(op, revOp[j][i]))
		}
		f[i+1] = res
	}
	return f[n]
}

func main() {
	word1 := "abcdf"
	word2 := "dacbe"
	result := minOperations(word1, word2)
	fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def minOperations(s: str, t: str) -> int:
    n = len(s)
    
    # 预处理 revOp
    revOp = [[0] * n for _ in range(n)]
    
    # 中心扩展法
    # i 为偶数表示奇长度子串，i 为奇数表示偶长度子串
    for i in range(2 * n - 1):
        cnt = [[0] * 26 for _ in range(26)]
        op = 1
        
        # 从闭区间 [l,r] 开始向左右扩展
        l = i // 2
        r = (i + 1) // 2
        
        while l >= 0 and r < n:
            # 定义update函数
            def update(x, y):
                nonlocal op
                if x == y:
                    return
                x_idx = ord(x) - ord('a')
                y_idx = ord(y) - ord('a')
                if cnt[y_idx][x_idx] > 0:
                    cnt[y_idx][x_idx] -= 1
                else:
                    cnt[x_idx][y_idx] += 1
                    op += 1
            
            update(s[l], t[r])
            if l != r:
                update(s[r], t[l])
            
            revOp[l][r] = op
            l -= 1
            r += 1
    
    # 动态规划部分
    f = [0] * (n + 1)
    
    for i in range(n):
        res = float('inf')
        cnt = [[0] * 26 for _ in range(26)]
        op = 0  # 不反转时的最小操作次数
        
        for j in range(i, -1, -1):
            # 定义update函数
            def update(x, y):
                nonlocal op
                if x == y:
                    return
                x_idx = ord(x) - ord('a')
                y_idx = ord(y) - ord('a')
                if cnt[y_idx][x_idx] > 0:
                    cnt[y_idx][x_idx] -= 1
                else:
                    cnt[x_idx][y_idx] += 1
                    op += 1
            
            update(s[j], t[j])
            res = min(res, f[j] + min(op, revOp[j][i]))
        
        f[i + 1] = res
    
    return f[n]

def main():
    word1 = "abcdf"
    word2 = "dacbe"
    result = minOperations(word1, word2)
    print(result)

if __name__ == "__main__":
    main()

C++完整代码如下：

#include <iostream>
#include <vector>
#include <string>
#include <climits>
#include <algorithm>

using namespace std;

int minOperations(string s, string t) {
    int n = s.length();

    // 预处理 revOp
    vector<vector<int>> revOp(n, vector<int>(n, 0));

    // 中心扩展法
    for (int i = 0; i < 2 * n - 1; i++) {
        vector<vector<int>> cnt(26, vector<int>(26, 0));
        int op = 1;

        // 从闭区间 [l,r] 开始向左右扩展
        int l = i / 2;
        int r = (i + 1) / 2;

        auto update = [&](char x, char y) {
            if (x == y) return;
            int x_idx = x - 'a';
            int y_idx = y - 'a';
            if (cnt[y_idx][x_idx] > 0) {
                cnt[y_idx][x_idx]--;
            } else {
                cnt[x_idx][y_idx]++;
                op++;
            }
        };

        while (l >= 0 && r < n) {
            update(s[l], t[r]);
            if (l != r) {
                update(s[r], t[l]);
            }
            revOp[l][r] = op;
            l--;
            r++;
        }
    }

    // 动态规划部分
    vector<int> f(n + 1, 0);

    for (int i = 0; i < n; i++) {
        int res = INT_MAX;
        vector<vector<int>> cnt(26, vector<int>(26, 0));
        int op = 0; // 不反转时的最小操作次数

        auto update = [&](char x, char y) {
            if (x == y) return;
            int x_idx = x - 'a';
            int y_idx = y - 'a';
            if (cnt[y_idx][x_idx] > 0) {
                cnt[y_idx][x_idx]--;
            } else {
                cnt[x_idx][y_idx]++;
                op++;
            }
        };

        for (int j = i; j >= 0; j--) {
            update(s[j], t[j]);
            res = min(res, f[j] + min(op, revOp[j][i]));
        }
        f[i + 1] = res;
    }

    return f[n];
}

int main() {
    string word1 = "abcdf";
    string word2 = "dacbe";
    int result = minOperations(word1, word2);
    cout << result << endl;
    return 0;
}