class Solution {
public:
int minOperations(string s1, string s2, int x) {
}
};
2896. 执行操作使两个字符串相等
给你两个下标从 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.length1 <= n, x <= 500s1 和 s2 只包含字符 '0' 和 '1' 。原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 2.7 MB, 提交时间: 2023-10-10 10:11:10
// dfs
func minOperations1(s1, s2 string, x int) int {
if strings.Count(s1, "1")%2 != strings.Count(s2, "1")%2 {
return -1
}
n := len(s1)
memo := make([][][2]int, n)
for i := range memo {
memo[i] = make([][2]int, n+1)
for j := range memo[i] {
memo[i][j] = [2]int{-1, -1}
}
}
var dfs func(int, int, int) int
dfs = func(i, j, preRev int) int {
if i < 0 {
if j > 0 || preRev > 0 {
return 1e9
}
return 0
}
p := &memo[i][j][preRev]
if *p != -1 {
return *p
}
if s1[i] == s2[i] == (preRev == 0) { // 无需反转
return dfs(i-1, j, 0)
}
res := min(dfs(i-1, j+1, 0)+x, dfs(i-1, j, 1)+1)
if j > 0 { // 可以免费反转
res = min(res, dfs(i-1, j-1, 0))
}
*p = res
return res
}
return dfs(n-1, 0, 0)
}
// 降维
func minOperations(s1, s2 string, x int) int {
if s1 == s2 {
return 0
}
p := []int{}
for i, c := range s1 {
if byte(c) != s2[i] {
p = append(p, i)
}
}
if len(p)%2 > 0 {
return -1
}
f0, f1 := 0, x
for i := 1; i < len(p); i++ {
f0, f1 = f1, min(f1+x, f0+(p[i]-p[i-1])*2)
}
return f1 / 2
}
func min(a, b int) int { if b < a { return b }; return a }
cpp 解法, 执行用时: 4 ms, 内存消耗: 7.3 MB, 提交时间: 2023-10-10 10:10:26
class Solution {
public:
// dfs
int minOperations1(string s1, string s2, int x) {
if (count(s1.begin(), s1.end(), '1') % 2 != count(s2.begin(), s2.end(), '1') % 2) {
return -1;
}
int n = s1.length();
int memo[n][n + 1][2];
memset(memo, -1, sizeof(memo)); // -1 表示没有计算过
function<int(int, int, bool)> dfs = [&](int i, int j, bool pre_rev) -> int {
if (i < 0) {
return j || pre_rev ? INT_MAX / 2 : 0;
}
int &res = memo[i][j][pre_rev]; // 注意这里是引用
if (res != -1) { // 之前计算过
return res;
}
if ((s1[i] == s2[i]) == !pre_rev) { // 无需反转
return dfs(i - 1, j, false);
}
res = min(dfs(i - 1, j + 1, false) + x, dfs(i - 1, j, true) + 1);
if (j) { // 可以免费反转
res = min(res, dfs(i - 1, j - 1, false));
}
return res;
};
return dfs(n - 1, 0, false);
}
// 降维
int minOperations(string s1, string s2, int x) {
if (s1 == s2) return 0;
vector<int> p;
for (int i = 0; i < s1.size(); i++)
if (s1[i] != s2[i])
p.push_back(i);
if (p.size() % 2) return -1;
int f0 = 0, f1 = x;
for (int i = 1; i < p.size(); i++) {
int new_f = min(f1 + x, f0 + (p[i] - p[i - 1]) * 2);
f0 = f1;
f1 = new_f;
}
return f1 / 2;
}
};
java 解法, 执行用时: 1 ms, 内存消耗: 40.8 MB, 提交时间: 2023-10-10 10:09:37
class Solution {
public int minOperations1(String s1, String s2, int x) {
char[] s = s1.toCharArray(), t = s2.toCharArray();
int n = s.length, diff = 0;
for (int i = 0; i < n; i++) {
if (s[i] != t[i]) {
diff ^= 1;
}
}
if (diff > 0) {
return -1;
}
int[][][] memo = new int[n][n + 1][2];
for (int i = 0; i < n; i++) {
for (int j = 0; j <= n; j++) {
Arrays.fill(memo[i][j], -1);// -1 表示没有计算过
}
}
return dfs(n - 1, 0, 0, memo, s, t, x);
}
private int dfs(int i, int j, int preRev, int[][][] memo, char[] s, char[] t, int x) {
if (i < 0) { // 递归边界
return j > 0 || preRev > 0 ? Integer.MAX_VALUE / 2 : 0;
}
if (memo[i][j][preRev] != -1) { // 之前计算过
return memo[i][j][preRev];
}
if ((s[i] == t[i]) == (preRev == 0)) { // 无需反转
return dfs(i - 1, j, 0, memo, s, t, x);
}
int res = Math.min(dfs(i - 1, j + 1, 0, memo, s, t, x) + x, dfs(i - 1, j, 1, memo, s, t, x) + 1);
if (j > 0) { // 可以免费反转
res = Math.min(res, dfs(i - 1, j - 1, 0, memo, s, t, x));
}
return memo[i][j][preRev] = res; // 记忆化
}
// 降维
public int minOperations(String s1, String s2, int x) {
if (s1.equals(s2)) {
return 0;
}
List<Integer> p = new ArrayList<>();
for (int i = 0; i < s1.length(); i++) {
if (s1.charAt(i) != s2.charAt(i)) {
p.add(i);
}
}
if (p.size() % 2 != 0) {
return -1;
}
int f0 = 0, f1 = x;
for (int i = 1; i < p.size(); i++) {
int newF = Math.min(f1 + x, f0 + (p.get(i) - p.get(i - 1)) * 2);
f0 = f1;
f1 = newF;
}
return f1 / 2;
}
}
python3 解法, 执行用时: 60 ms, 内存消耗: 16.2 MB, 提交时间: 2023-10-10 10:09:01
class Solution:
def minOperations1(self, s1: str, s2: str, x: int) -> int:
if s1.count('1') % 2 != s2.count('1') % 2:
return -1
@cache
def dfs(i: int, j: int, pre_rev: bool) -> int:
if i < 0:
return inf if j or pre_rev else 0
if (s1[i] == s2[i]) == (not pre_rev): # 无需反转
return dfs(i - 1, j, False)
res = min(dfs(i - 1, j + 1, False) + x, dfs(i - 1, j, True) + 1)
if j: # 可以免费反转
res = min(res, dfs(i - 1, j - 1, False))
return res
return dfs(len(s1) - 1, 0, False)
# 降维
def minOperations(self, s1: str, s2: str, x: int) -> int:
if s1 == s2:
return 0
p = [i for i, (x, y) in enumerate(zip(s1, s2)) if x != y]
if len(p) % 2:
return -1
f0, f1 = 0, x
for i, j in pairwise(p):
f0, f1 = f1, min(f1 + x, f0 + (j - i) * 2)
return f1 // 2