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 := range2*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-*-
defminOperations(s: str, t: str) -> int:
n = len(s)
# 预处理 revOp
revOp = [[0] * n for _ inrange(n)]
# 中心扩展法
# i 为偶数表明奇长度子串，i 为奇数表明偶长度子串
for i inrange(2 * n - 1):
cnt = [[0] * 26for _ inrange(26)]
op = 1
# 从闭区间 [l,r] 开始向左右扩展
l = i // 2
r = (i + 1) // 2
while l >= 0and r < n:
# 定义update函数
defupdate(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 inrange(n):
res = float('inf')
cnt = [[0] * 26for _ inrange(26)]
op = 0# 不反转时的最小操作次数
for j inrange(i, -1, -1):
# 定义update函数
defupdate(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]
defmain():
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>
usingnamespace 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;
return0;
}我们信任人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。
欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
相关文章
您必须登录才能参与评论！
立即登录
收藏了，感谢分享