Medium

题目描述

给你两个长度为 n 的 0 索引二进制字符串 s1 和 s2，以及一个正整数 x。

你可以对字符串 s1 执行以下操作任意次：

  • 选择两个下标 i 和 j，翻转 s1[i] 和 s1[j]。这个操作的代价是 x。
  • 选择满足 i < n - 1 的下标 i，翻转 s1[i] 和 s1[i + 1]。这个操作的代价是 1。

返回使字符串 s1 和 s2 相等所需的最小代价，如果无法实现则返回 -1。

注意，翻转字符是指将字符从 ‘0’ 变为 ‘1’，或者从 ‘1’ 变为 ‘0’。

示例 1：

输入：s1 = "1100011000", s2 = "0101001010", x = 2
输出：4
解释：我们可以执行以下操作：
- 选择 i = 3，执行第二种操作。结果字符串为 s1 = "1101111000"。
- 选择 i = 4，执行第二种操作。结果字符串为 s1 = "1101001000"。
- 选择 i = 0 和 j = 8，执行第一种操作。结果字符串为 s1 = "0101001010" = s2。
总代价为 1 + 1 + 2 = 4。可以证明这是可能的最小代价。

示例 2：

输入：s1 = "10110", s2 = "00011", x = 4
输出：-1
解释：无法使两个字符串相等。

提示：

  • n == s1.length == s2.length
  • 1 <= n, x <= 500
  • s1 和 s2 只包含字符 ‘0’ 和 ‘1’

解题思路

这道题的核心是分析翻转操作的性质和找到最优策略。

首先分析问题的可行性：每次操作都翻转偶数个字符，所以如果两个字符串不同位置的数量是奇数，则无解。

接下来分析操作策略：

  1. 操作1（代价x）：可以翻转任意两个位置
  2. 操作2（代价1）：只能翻转相邻的两个位置

关键观察：我们只关心 s1 和 s2 不同的位置。设这些位置为 diff 数组。

对于 diff 数组中的位置，我们有两种处理方式：

  • 使用操作2：将相邻的不同位置配对，每对代价为2（因为需要2次相邻翻转）
  • 使用操作1：将任意两个不同位置配对，每对代价为x

这就变成了一个动态规划问题：如何以最小代价将 diff 数组中的位置全部配对。

状态定义：dp[i] 表示处理前 i 个不同位置的最小代价

转移方程：

  • 如果第 i-1 和第 i-2 个位置相邻：dp[i] = min(dp[i-2] + 2, dp[i-2] + x)
  • 如果不相邻：dp[i] = dp[i-2] + x

最终答案需要除以2，因为我们计算的是每个位置的翻转代价，但实际上每次操作会同时处理两个位置。

代码实现

class Solution {
public:
    int minOperations(string s1, string s2, int x) {
        vector<int> diff;
        for (int i = 0; i < s1.length(); i++) {
            if (s1[i] != s2[i]) {
                diff.push_back(i);
            }
        }
        
        int n = diff.size();
        if (n % 2 == 1) return -1;
        if (n == 0) return 0;
        
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        
        for (int i = 2; i <= n; i += 2) {
            // 用操作1配对第i-1和i-2个位置
            dp[i] = dp[i-2] + x;
            
            // 如果第i-1和i-2个位置相邻，可以用操作2
            if (diff[i-1] - diff[i-2] == 1) {
                dp[i] = min(dp[i], dp[i-2] + 2);
            }
            
            // 尝试所有可能的配对方式
            for (int j = i - 4; j >= 0; j -= 2) {
                int cost = dp[j] + (i - j) / 2 * x;
                for (int k = j; k < i - 1; k++) {
                    if (diff[k+1] - diff[k] == 1) {
                        cost = min(cost, dp[j] + (k - j) / 2 * x + 2 + (i - k - 2) / 2 * x);
                    }
                }
                dp[i] = min(dp[i], cost);
            }
        }
        
        return dp[n];
    }
};

class Solution:
    def minOperations(self, s1: str, s2: str, x: int) -> int:
        diff = []
        for i in range(len(s1)):
            if s1[i] != s2[i]:
                diff.append(i)
        
        n = len(diff)
        if n % 2 == 1:
            return -1
        if n == 0:
            return 0
        
        # dp[i] 表示处理前i个不同位置的最小代价
        dp = [float('inf')] * (n + 1)
        dp[0] = 0
        
        for i in range(2, n + 1, 2):
            # 用操作1配对最后两个位置
            dp[i] = dp[i-2] + x
            
            # 如果最后两个位置相邻，可以用操作2
            if diff[i-1] - diff[i-2] == 1:
                dp[i] = min(dp[i], dp[i-2] + 2)
        
        return dp[n]

public class Solution {
    public int MinOperations(string s1, string s2, int x) {
        var diff = new List<int>();
        for (int i = 0; i < s1.Length; i++) {
            if (s1[i] != s2[i]) {
                diff.Add(i);
            }
        }
        
        int n = diff.Count;
        if (n % 2 == 1) return -1;
        if (n == 0) return 0;
        
        int[] dp = new int[n + 1];
        Array.Fill(dp, int.MaxValue);
        dp[0] = 0;
        
        for (int i = 2; i <= n; i += 2) {
            // 用操作1配对最后两个位置
            dp[i] = dp[i-2] + x;
            
            // 如果最后两个位置相邻，可以用操作2
            if (diff[i-1] - diff[i-2] == 1) {
                dp[i] = Math.Min(dp[i], dp[i-2] + 2);
            }
        }
        
        return dp[n];
    }
}

var minOperations = function(s1, s2, x) {
    const n = s1.length;
    const diff = [];
    
    for (let i = 0; i < n; i++) {
        if (s1[i] !== s2[i]) {
            diff.push(i);
        }
    }
    
    const m = diff.length;
    if (m % 2 === 1) return -1;
    if (m === 0) return 0;
    
    const dp = new Array(m + 1).fill(Infinity);
    dp[0] = 0;
    
    for (let i = 2; i <= m; i += 2) {
        dp[i] = dp[i - 2] + Math.min(x, diff[i - 1] - diff[i - 2]);
        
        for (let j = 2; j < i; j += 2) {
            dp[i] = Math.min(dp[i], dp[j] + dp[i - j]);
        }
    }
    
    return dp[m];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

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

其中 n 为字符串长度。时间复杂度主要来自于遍历字符串找出不同位置和动态规划计算，空间复杂度主要用于存储不同位置数组和 dp 数组。