Medium

题目描述

给定两个二进制字符串 s 和 t，长度都为 n，以及三个正整数 flipCost、swapCost 和 crossCost。

你可以对字符串 s 和 t 执行以下操作任意次数（以任意顺序）：

  1. 选择任意索引 i，翻转 s[i] 或 t[i]（将 ‘0’ 变为 ‘1’ 或将 ‘1’ 变为 ‘0’）。此操作的成本为 flipCost。
  2. 选择两个不同的索引 i 和 j，交换 s[i] 和 s[j] 或交换 t[i] 和 t[j]。此操作的成本为 swapCost。
  3. 选择索引 i，交换 s[i] 和 t[i]。此操作的成本为 crossCost。

返回使字符串 s 和 t 相等所需的最小总成本。

示例 1：

输入：s = "01000", t = "10111", flipCost = 10, swapCost = 2, crossCost = 2
输出：16

示例 2：

输入：s = "001", t = "110", flipCost = 2, swapCost = 100, crossCost = 100
输出：6

示例 3：

输入：s = "1010", t = "1010", flipCost = 5, swapCost = 5, crossCost = 5
输出：0

约束条件：

  • n == s.length == t.length
  • 1 <= n <= 10^5
  • 1 <= flipCost, swapCost, crossCost <= 10^9
  • s 和 t 只包含字符 ‘0’ 和 ‘1’

解题思路

这是一道贪心算法题，需要分析不同类型的不匹配情况并选择最优的修复策略。

核心思路：

  1. 统计不匹配类型：遍历字符串，统计两种不匹配情况：

    • a：s[i] = '0' 且 t[i] = '1' 的位置数量
    • b：s[i] = '1' 且 t[i] = '0' 的位置数量

  2. 处理相反的不匹配对：对于每一对相反的不匹配（一个 (0,1) 和一个 (1,0)），有两种修复方式：

    • 使用交换操作：成本为 swapCost
    • 使用两次翻转操作：成本为 2 * flipCost
    • 选择较小的成本：min(swapCost, 2 * flipCost)

  3. 处理剩余的不匹配：配对后剩余 r = |a - b| 个不匹配，这些必须成对处理：

    • 每对可以用交叉交换 + 同字符串交换：成本为 crossCost + swapCost
    • 或者用两次翻转：成本为 2 * flipCost
    • 选择较小的成本：min(crossCost + swapCost, 2 * flipCost)

  4. 处理最后的单个不匹配：如果剩余数量为奇数，最后一个只能用翻转修复，成本为 flipCost。

代码实现

class Solution {
public:
    long long minimumCost(string s, string t, int flipCost, int swapCost, int crossCost) {
        int n = s.length();
        int a = 0, b = 0;
        
        // 统计不匹配类型
        for (int i = 0; i < n; i++) {
            if (s[i] == '0' && t[i] == '1') a++;
            else if (s[i] == '1' && t[i] == '0') b++;
        }
        
        long long cost = 0;
        
        // 处理相反的不匹配对
        int pairs = min(a, b);
        cost += (long long)pairs * min(swapCost, 2 * flipCost);
        
        // 更新剩余的不匹配数量
        a -= pairs;
        b -= pairs;
        int remaining = a + b;
        
        // 处理剩余的不匹配（成对处理）
        int remainingPairs = remaining / 2;
        cost += (long long)remainingPairs * min(crossCost + swapCost, 2 * flipCost);
        
        // 处理最后的单个不匹配（如果存在）
        if (remaining % 2 == 1) {
            cost += flipCost;
        }
        
        return cost;
    }
};

class Solution:
    def minimumCost(self, s: str, t: str, flipCost: int, swapCost: int, crossCost: int) -> int:
        n = len(s)
        a = 0  # s[i] = '0', t[i] = '1'
        b = 0  # s[i] = '1', t[i] = '0'
        
        # 统计不匹配类型
        for i in range(n):
            if s[i] == '0' and t[i] == '1':
                a += 1
            elif s[i] == '1' and t[i] == '0':
                b += 1
        
        cost = 0
        
        # 处理相反的不匹配对
        pairs = min(a, b)
        cost += pairs * min(swapCost, 2 * flipCost)
        
        # 更新剩余的不匹配数量
        a -= pairs
        b -= pairs
        remaining = a + b
        
        # 处理剩余的不匹配（成对处理）
        remaining_pairs = remaining // 2
        cost += remaining_pairs * min(crossCost + swapCost, 2 * flipCost)
        
        # 处理最后的单个不匹配（如果存在）
        if remaining % 2 == 1:
            cost += flipCost
        
        return cost

public class Solution {
    public long MinimumCost(string s, string t, int flipCost, int swapCost, int crossCost) {
        int n = s.Length;
        int a = 0, b = 0;
        
        // 统计不匹配类型
        for (int i = 0; i < n; i++) {
            if (s[i] == '0' && t[i] == '1') a++;
            else if (s[i] == '1' && t[i] == '0') b++;
        }
        
        long cost = 0;
        
        // 处理相反的不匹配对
        int pairs = Math.Min(a, b);
        cost += (long)pairs * Math.Min(swapCost, 2 * flipCost);
        
        // 更新剩余的不匹配数量
        a -= pairs;
        b -= pairs;
        int remaining = a + b;
        
        // 处理剩余的不匹配（成对处理）
        int remainingPairs = remaining / 2;
        cost += (long)remainingPairs * Math.Min(crossCost + swapCost, 2 * flipCost);
        
        // 处理最后的单个不匹配（如果存在）
        if (remaining % 2 == 1) {
            cost += flipCost;
        }
        
        return cost;
    }
}

var minimumCost = function(s, t, flipCost, swapCost, crossCost) {
    const n = s.length;
    let a = 0, b = 0;
    
    // 统计不匹配类型
    for (let i = 0; i < n; i++) {
        if (s[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

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

其中 n 是字符串的长度。算法只需要遍历一次字符串来统计不匹配情况，然后进行常数时间的计算。