Hard

题目描述

给定两个长度相等的字符串 word1 和 word2。你需要将 word1 转换为 word2。

为此，将 word1 分割成一个或多个连续子串。对于每个子串 substr，你可以执行以下操作：

  • 替换：将 substr 中任意一个位置的字符替换为另一个小写英文字母。
  • 交换：交换 substr 中的任意两个字符。
  • 反转子串：反转 substr。

每个操作计为一步，每个子串的每个字符在每种操作类型中最多只能使用一次（即，任何单个索引在替换、交换或反转操作中最多只能参与一次）。

返回将 word1 转换为 word2 所需的最小操作数。

示例 1：

输入：word1 = "abcdf", word2 = "dacbe"
输出：4

示例 2：

输入：word1 = "abceded", word2 = "baecfef"
输出：4

示例 3：

输入：word1 = "abcdef", word2 = "fedabc"
输出：2

约束条件：

  • 1 <= word1.length == word2.length <= 100
  • word1 和 word2 仅包含小写英文字母。

解题思路

这是一个复杂的动态规划问题。关键思路如下：

核心思想：对于字符串的每个子串，我们需要计算将其转换为目标子串的最小操作数。由于可以对子串进行反转操作，所以每个子串实际上有两种形态：原始形态和反转后的形态。

动态规划状态：

  • dp[i][j] 表示将 word1[0...i-1] 转换为 word2[0...j-1] 的最小操作数
  • 对于每个子串，我们需要考虑是否反转它，然后计算最优的操作组合

子串操作优化： 对于一个子串，最优策略是：

  1. 首先使用交换操作：如果 word1[i] == word2[j] 且 word1[j] == word2[i]，可以通过一次交换同时修复两个位置
  2. 然后对剩余不匹配的字符使用替换操作

算法步骤：

  1. 使用动态规划枚举所有可能的子串分割方式
  2. 对每个子串，计算原始状态和反转状态的最小操作数
  3. 反转操作本身需要 1 步，所以反转状态需要额外加 1
  4. 选择最优方案

时间复杂度为 O(n³)，空间复杂度为 O(n²)。

代码实现

class Solution {
public:
    int minOperations(string word1, string word2) {
        int n = word1.length();
        vector<vector<int>> dp(n + 1, vector<int>(n + 1, INT_MAX));
        dp[0][0] = 0;
        
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                if (dp[i][j] == INT_MAX) continue;
                
                // Try all possible next substrings
                for (int len = 1; i + len <= n && j + len <= n; len++) {
                    string s1 = word1.substr(i, len);
                    string s2 = word2.substr(j, len);
                    
                    // Calculate cost without reverse
                    int cost1 = getCost(s1, s2);
                    dp[i + len][j + len] = min(dp[i + len][j + len], dp[i][j] + cost1);
                    
                    // Calculate cost with reverse (add 1 for reverse operation)
                    reverse(s1.begin(), s1.end());
                    int cost2 = getCost(s1, s2) + 1;
                    dp[i + len][j + len] = min(dp[i + len][j + len], dp[i][j] + cost2);
                }
            }
        }
        
        return dp[n][n];
    }
    
private:
    int getCost(string s1, string s2) {
        int n = s1.length();
        vector<bool> used(n, false);
        int operations = 0;
        
        // First, perform swaps
        for (int i = 0; i < n; i++) {
            if (used[i] || s1[i] == s2[i]) continue;
            for (int j = i + 1; j < n; j++) {
                if (used[j] || s1[j] == s2[j]) continue;
                if (s1[i] == s2[j] && s1[j] == s2[i]) {
                    used[i] = used[j] = true;
                    operations++;
                    break;
                }
            }
        }
        
        // Then, perform replacements
        for (int i = 0; i < n; i++) {
            if (!used[i] && s1[i] != s2[i]) {
                operations++;
            }
        }
        
        return operations;
    }
};

class Solution:
    def minOperations(self, word1: str, word2: str) -> int:
        n = len(word1)
        dp = [[float('inf')] * (n + 1) for _ in range(n + 1)]
        dp[0][0] = 0
        
        for i in range(n + 1):
            for j in range(n + 1):
                if dp[i][j] == float('inf'):
                    continue
                
                # Try all possible next substrings
                for length in range(1, n - max(i, j) + 1):
                    if i + length > n or j + length > n:
                        break
                    
                    s1 = word1[i:i + length]
                    s2 = word2[j:j + length]
                    
                    # Calculate cost without reverse
                    cost1 = self.getCost(s1, s2)
                    dp[i + length][j + length] = min(dp[i + length][j + length], 
                                                   dp[i][j] + cost1)
                    
                    # Calculate cost with reverse (add 1 for reverse operation)
                    s1_rev = s1[::-1]
                    cost2 = self.getCost(s1_rev, s2) + 1
                    dp[i + length][j + length] = min(dp[i + length][j + length], 
                                                   dp[i][j] + cost2)
        
        return dp[n][n]
    
    def getCost(self, s1: str, s2: str) -> int:
        n = len(s1)
        used = [False] * n
        operations = 0
        
        # First, perform swaps
        for i in range(n):
            if used[i] or s1[i] == s2[i]:
                continue
            for j in range(i + 1, n):
                if used[j] or s1[j] == s2[j]:
                    continue
                if s1[i] == s2[j] and s1[j] == s2[i]:
                    used[i] = used[j] = True
                    operations += 1
                    break
        
        # Then, perform replacements
        for i in range(n):
            if not used[i] and s1[i] != s2[i]:
                operations += 1
        
        return operations

public class Solution {
    public int MinOperations(string word1, string word2) {
        int n = word1.Length;
        int[,] dp = new int[n + 1, n + 1];
        
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                dp[i, j] = int.MaxValue;
            }
        }
        dp[0, 0] = 0;
        
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                if (dp[i, j] == int.MaxValue) continue;
                
                for (int len = 1; i + len <= n && j + len <= n; len++) {
                    string s1 = word1.Substring(i, len);
                    string s2 = word2.Substring(j, len);
                    
                    int cost1 = GetCost(s1, s2);
                    dp[i + len, j + len] = Math.Min(dp[i + len, j + len], dp[i, j] + cost1);
                    
                    char[] arr = s1.ToCharArray();
                    Array.Reverse(arr);
                    string s1Rev = new string(arr);
                    int cost2 = GetCost(s1Rev, s2) + 1;
                    dp[i + len, j + len] = Math.Min(dp[i + len, j + len], dp[i, j] + cost2);
                }
            }
        }
        
        return dp[n, n];
    }
    
    private int GetCost(string s1, string s2) {
        int n = s1.Length;
        bool[] used = new bool[n];
        int operations = 0;
        
        for (int i = 0; i < n; i++) {
            if (used[i] || s1[i] == s2[i]) continue;
            for (int j = i + 1; j < n; j++) {
                if (used[j] || s1[j] == s2[j]) continue;
                if (s1[i] == s2[j] && s1[j] == s2[i]) {
                    used[i] = used[j] = true;
                    operations++;
                    break;
                }
            }
        }
        
        for (int i = 0; i < n; i++) {
            if (!used[i] && s1[i] != s2[i]) {
                operations++;
            }
        }
        
        return operations;
    }
}

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minOperations = function(word1, word2) {
    const n = word1.length;
    const memo = new Map();
    
    function dp(i) {
        if (i === n) return 0;
        if (memo.has(i)) return memo.get(i);
        
        let minOps = Infinity;
        
        for (let j = i; j < n; j++) {
            const substr1 = word1.slice(i, j + 1);
            const substr2 = word2.slice(i, j + 1);
            const ops = getMinOps(substr1, substr2);
            minOps = Math.min(minOps, ops + dp(j + 1));
        }
        
        memo.set(i, minOps);
        return minOps;
    }
    
    function getMinOps(s1, s2) {
        const len = s1.length;
        let minOps = Infinity;
        
        // Try all possible combinations of operations
        for (let reverse = 0; reverse < 2; reverse++) {
            let curr = s1;
            let ops = 0;
            
            if (reverse) {
                curr = curr.split('').reverse().join('');
                ops++;
            }
            
            // Count character frequencies
            const freq1 = {};
            const freq2 = {};
            for (let i = 0; i < len; i++) {
                freq1[curr[i]] = (freq1[curr[i]] || 0) + 1;
                freq2[s2[i]] = (freq2[s2[i]] || 0) + 1;
            }
            
            // Calculate swaps needed
            let swaps = 0;
            const chars1 = Object.keys(freq1);
            const chars2 = Object.keys(freq2);
            
            for (const char of chars1) {
                if (freq2[char]) {
                    swaps += Math.min(freq1[char], freq2[char]);
                }
            }
            
            // Remaining characters need replacement
            const totalMatched = swaps;
            const replacements = len - totalMatched;
            
            // Swaps operations needed (each swap fixes 2 positions if both need swapping)
            const swapOps = Math.floor(swaps / 2);
            const remainingAfterSwaps = swaps % 2;
            
            ops += swapOps + remainingAfterSwaps + replacements;
            minOps = Math.min(minOps, ops);
        }
        
        return minOps;
    }
    
    return dp(0);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n³)
空间复杂度O(n²)

相关题目