执行操作使两个字符串相等
难度:
标签:
题目描述
You are given two 0-indexed binary strings s1 and s2, both of length n, and a positive integer x.
You can perform any of the following operations on the string s1 any number of times:
- Choose two indices
iandj, and flip boths1[i]ands1[j]. The cost of this operation isx. - Choose an index
isuch thati < n - 1and flip boths1[i]ands1[i + 1]. The cost of this operation is1.
Return the minimum cost needed to make the strings s1 and s2 equal, or return -1 if it is impossible.
Note that flipping a character means changing it from 0 to 1 or vice-versa.
Example 1:
Input: s1 = "1100011000", s2 = "0101001010", x = 2 Output: 4 Explanation: We can do the following operations: - Choose i = 3 and apply the second operation. The resulting string is s1 = "1101111000". - Choose i = 4 and apply the second operation. The resulting string is s1 = "1101001000". - Choose i = 0 and j = 8 and apply the first operation. The resulting string is s1 = "0101001010" = s2. The total cost is 1 + 1 + 2 = 4. It can be shown that it is the minimum cost possible.
Example 2:
Input: s1 = "10110", s2 = "00011", x = 4 Output: -1 Explanation: It is not possible to make the two strings equal.
Constraints:
n == s1.length == s2.length1 <= n, x <= 500s1ands2consist only of the characters'0'and'1'.
代码结果
运行时间: 30 ms, 内存: 16.1 MB
/*
* 题目思路：
* 我们需要通过反转操作使s1和s2相等。
* 1. 首先，我们记录所有不同的位置的下标。
* 2. 然后，优先使用第二种操作将相邻的不同位置反转，代价为1。
* 3. 对于不相邻的不同位置，如果x的代价小于两次第二种操作的代价，我们选择第一种操作，代价为x。
* 4. 最终计算最小代价，如果不能使两者相等，返回-1。
*/
import java.util.stream.IntStream;
public class Solution {
public int minCost(String s1, String s2, int x) {
int n = s1.length();
int[] diffIndices = IntStream.range(0, n)
.filter(i -> s1.charAt(i) != s2.charAt(i))
.toArray();
int diffCount = diffIndices.length;
if (diffCount == 0) return 0; // 已经相等
if (diffCount % 2 != 0) return -1; // 奇数个不同，无法使其相等
int cost = 0;
int i = 0;
// 处理相邻的不同位置
while (i < diffCount - 1) {
if (diffIndices[i + 1] == diffIndices[i] + 1) {
cost += 1;
i += 2;
} else {
i += 1;
}
}
// 处理不相邻的不同位置
for (int j = i; j < diffCount; j += 2) {
cost += Math.min(2, x);
}
return cost;
}
}解释
方法:
题解通过首先比较两个字符串s1和s2的每个对应字符，找出所有不同的位置。然后检查不同位置的个数，如果是奇数，则返回-1，因为每次操作至少修改两个字符。对于偶数个不同位置，题解采用动态规划的方法，用a和b来存储当前和下一步的最小代价。对于每一对不同位置，计算通过直接交换这两个位置的字符或者通过一系列操作让这两个位置的字符相同的最小代价，更新a和b的值。最后返回代价b除以2的值。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么在不同字符数量为奇数时直接返回-1？这意味着什么样的情况下无法通过任何操作使得s1和s2相等？
▷🦆
在对每对索引计算最小代价时，表达式`b + x`和`a + (j - i) * 2`分别代表什么含义？为什么选择这两种方式计算代价？
▷🦆
对于`pairwise(idxs)`函数的使用，这个函数是如何工作的，它如何帮助在题解中处理索引对？
▷