2896. 执行操作使两个字符串相等(2172)

给你两个下标从 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：

1
2
3
4
5
6
7
输入：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：

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

提示：

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

条件转换 + 一维线性dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int minOperations(String s1, String s2, int x) {
        int n = s1.length(), res = 0;
        List<Integer> indexes = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (s1.charAt(i) != s2.charAt(i)) {
                indexes.add(i);
            }
        }
        int sz = indexes.size();
        if (sz % 2 != 0) return -1;
        // 反转2个位置需要花费x，所以可以花费x/2反转1个位置（必然会会花费x/2反转两次1个位置）
        // f[i] = min(f[i-1] + x/2, f[i-2] + indexes[i] - indexes[i-1])
        // 由于x/2会被取整，所以下面在dp过程都加上2倍的值，最后返回结果除以2
        int dp[] = new int[sz+1];
        for (int i = 1; i <= sz; i++) {
            dp[i] = Math.min(dp[i-1] + x, i-2 >= 0 ? dp[i-2] + (indexes.get(i-1) - indexes.get(i-2))*2 : Integer.MAX_VALUE);
        }
        return dp[sz]/2;
    }
}