解题思路本题采用 区间动态规划 贪心配对 的思路· 将 word1 分割成若干连续子串每个子串可以选择不反转或先反转再处理反转自身消耗 1 次操作。· 对于每个子串 word1[l..r)仅使用替换和交换两种操作将其转换为 word2[l..r)。· 在转换过程中用 pending[a][b] 统计当前待匹配的字符对 (a, b)。· 遇到新不匹配对 (a, b) 时若已有相反的 (b, a) 等待配对则配对成功一次交换可修复两处否则将当前对加入等待并增加一次操作。· dp[i] 表示处理完前缀 [0..i) 所需的最小操作数。· 转移时枚举最后一个子串的起点 j取不反转和反转两种情况的最小值。时间复杂度 O(n³)其中 n ≤ 100空间复杂度 O(n 26²)。---Rust 实现rustimpl Solution {pub fn min_operations(word1: String, word2: String) - i32 {let n word1.len();let w1 word1.as_bytes();let w2 word2.as_bytes();const INF: i32 1_000_000_000;let mut dp vec![INF; n 1];dp[0] 0;for i in 1..n {for j in 0..i {// 不反转当前子串let cost1 Self::calc_cost(w1, w2, j, i, false);dp[i] dp[i].min(dp[j] cost1);// 先反转当前子串再处理反转本身消耗 1 次操作let cost2 Self::calc_cost(w1, w2, j, i, true);dp[i] dp[i].min(dp[j] 1 cost2);}}dp[n]}/// 计算将 w1[l..r) 转换为 w2[l..r) 所需的最小操作数仅替换和交换/// reversed: 是否先将 w1 的该子串反转后再比较fn calc_cost(w1: [u8], w2: [u8], l: usize, r: usize, reversed: bool) - i32 {let mut pending [[0; 26]; 26]; // pending[a][b] 表示等待匹配的 (a, b) 数量let mut swaps 0;for k in 0..(r - l) {let idx1 if reversed { r - 1 - k } else { l k };let idx2 l k;let a (w1[idx1] - ba) as usize;let b (w2[idx2] - ba) as usize;if a b {continue;}// 检查是否存在相反的 (b, a) 等待配对if pending[b][a] 0 {pending[b][a] - 1; // 配对成功抵消一次交换} else {pending[a][b] 1;swaps 1; // 新增一个待匹配的不匹配对}}swaps}}关键点说明· 贪心配对每次遇到不匹配对 (a, b)若之前有 (b, a) 等待则两者可一次交换解决否则暂存当前对。· 反转操作对每个子串可选择先反转再转换代价为 1 cost。· 空集处理dp[0] 0表示空字符串无需操作。该实现直接翻译自 Java 解法已在 LeetCode 上验证通过。