执行操作使两个字符串相等

难度: Medium

给你两个下标从 0 开始的二进制字符串 s1 和 s2 ，两个字符串的长度都是 n ，再给你一个正整数 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' 。

Submission

运行时间: 30 ms

内存: 16.1 MB

class Solution:
    def minOperations(self, s1: str, s2: str, x: int) -> int:
        idxs = [idx for idx, (i, j) in enumerate(zip(s1, s2)) if i != j]
        m = len(idxs)
        if m == 0:
            return 0
        if m % 2:
            return -1
        a, b = 0, x
        for i, j in pairwise(idxs):
            c = min(b + x, a + (j - i) * 2)
            a, b = b, c
        return b // 2

Explain

题解通过首先比较两个字符串s1和s2的每个对应字符，找出所有不同的位置。然后检查不同位置的个数，如果是奇数，则返回-1，因为每次操作至少修改两个字符。对于偶数个不同位置，题解采用动态规划的方法，用a和b来存储当前和下一步的最小代价。对于每一对不同位置，计算通过直接交换这两个位置的字符或者通过一系列操作让这两个位置的字符相同的最小代价，更新a和b的值。最后返回代价b除以2的值。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def minOperations(self, s1: str, s2: str, x: int) -> int:
        # 生成不同字符位置的索引列表
        idxs = [idx for idx, (i, j) in enumerate(zip(s1, s2)) if i != j]
        m = len(idxs)
        if m == 0:  # 如果没有不同字符，返回0
            return 0
        if m % 2:  # 如果不同字符数量为奇数，返回-1
            return -1
        a, b = 0, x
        for i, j in pairwise(idxs):  # 对每对索引计算最小代价
            c = min(b + x, a + (j - i) * 2)  # b+x代表跳过一个不匹配，a+(j-i)*2代表解决当前不匹配
            a, b = b, c  # 更新代价值
        return b // 2  # 返回总代价

Explore

当不同字符的数量为奇数时，意味着至少有一个字符无法找到另一个不同的字符与之配对进行交换或变更操作。每次操作至少涉及两个字符的修改，如果剩下一个单独的不同字符，就没有办法通过一次操作解决这个不匹配，因此无法通过任何操作使两个字符串完全相等。

在这个题解中，`b + x`代表使用之前的最小代价（b）并加上一次新的操作成本（x），这表示跳过一个当前不匹配的位置并处理下一个。而`a + (j - i) * 2`代表使用上一个不匹配（a）的代价，并加上当前位置到下一个不匹配位置的距离乘以2，这代表解决当前的不匹配（通过修改两个字符的方式）。选择这两种方式是为了确保能找到在当前步骤中可能的最小操作成本，从而整体上达到最小化修改字符串的总代价。

`pairwise`函数用于生成一个迭代器，这个迭代器会返回原始列表中每对相邻元素的元组，例如，列表[1, 2, 3, 4]会被`pairwise`处理成[(1, 2), (2, 3), (3, 4)]。在本题解中，使用`pairwise(idxs)`帮助处理每一对不同字符的索引，这是因为每次操作都会考虑两个不同位置的字符，从而计算这两个位置间的最小代价。这样可以直接在两个不同字符之间建立关联，计算出最优解。