解题思路采用区间DP 贪心匹配· 核心操作可以将 word1 分割成若干连续子串对每个子串可执行替换、交换、反转三种操作。· 贪心匹配处理一个子串时遇到不匹配的字符对 (a, b)优先寻找之前是否出现过相反的不匹配对 (b, a)。如果找到说明这两个位置可以一次交换同时修复否则记录当前不匹配对等待后续配对。· DP定义dp[i] 表示将 word1[0..i-1] 转换为 word2[0..i-1] 的最小操作数。· 状态转移枚举最后一个子串的起点 j取不反转和先反转两种情况的最小值· dp[i] min(dp[i], dp[j] cost(j, i, false))· dp[i] min(dp[i], dp[j] 1 cost(j, i, true))---Java 实现javaclass Solution {public int minOperations(String word1, String word2) {int n word1.length();int[] dp new int[n 1];for (int i 1; i n; i) {dp[i] Integer.MAX_VALUE;}dp[0] 0;for (int i 1; i n; i) {for (int j 0; j i; j) {// 情况1不反转子串 word1[j..i-1]int cost1 calcCost(word1, word2, j, i, false);dp[i] Math.min(dp[i], dp[j] cost1);// 情况2先反转子串 word1[j..i-1]再处理反转本身消耗1次操作int cost2 calcCost(word1, word2, j, i, true);dp[i] Math.min(dp[i], dp[j] 1 cost2);}}return dp[n];}/*** 计算将 word1[l..r-1] 转换为 word2[l..r-1] 所需的最少操作数只使用替换和交换。* param reversed true 表示先将 word1 的这段子串反转再与 word2 对应位置比较*/private int calcCost(String word1, String word2, int l, int r, boolean reversed) {int[][] pending new int[26][26]; // pending[a][b] 表示等待匹配的 (a, b) 数量int swaps 0; // 交换操作次数 不匹配对数量for (int k 0; k r - l; k) {int idx1 reversed ? r - 1 - k : l k;int idx2 l k;int a word1.charAt(idx1) - a;int b word2.charAt(idx2) - a;if (a b) continue;// 检查是否有相反的 (b, a) 等待配对if (pending[b][a] 0) {pending[b][a]--; // 配对成功抵消一次交换} else {pending[a][b];swaps; // 新增一个待匹配的不匹配对}}return swaps; // 每个不匹配对需要一次交换或替换操作}}---复杂度分析· 时间复杂度O(n³)其中 n ≤ 100。外层枚举 i 和 j 共 O(n²) 种子串calcCost 遍历子串长度 O(n)总计 O(n³)。· 空间复杂度O(n 26²)dp 数组 O(n)计数数组 O(26²) 为常数。
