题目描述
给你两个下标从 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
。
样例
输入: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。这是最小代价和。
输入:s1 = "10110", s2 = "00011", x = 4
输出:-1
解释:无法使两个字符串相等。
限制
n == s1.length == s2.length
1 <= n, x <= 500
s1
和s2
只包含字符'0'
和'1'
。
算法1
(动态规划) $O(n^2)$
- 我们假设两个字符相同值的位置为 $0$,不同值的位置为 $1$。
- 设状态 $f(i)$ 表示以 $i$ 为结尾的前缀字符串,全部为 $0$ 的最小代价。$g(i)$ 表示以 $i$ 为结尾的字符串,除了 $i$ 位置为 $1$ 外,其余前缀均为 $0$ 的最小代价。
- 初始时,如果 $s1(0) = s2(0)$,则 $f(0) = 0$,否则 $g(0) = 0$,其余均为正无穷待定。
- 转移时,针对当前位置 $i$,枚举前缀结束位置 $j$。如果 $i$ 位置两个字符相同,则可以转移 $f(i) = f(j) + cost(j + 1, i, 0)$,以及 $g(i) = g(j) + cost(j + 1, i, c)$;如果 $i$ 位置不同,则可以转移 $f(i) = g(j) + cost(j + 1, i, c)$,以及 $g(i) = f(j) + cost(j + 1, i, 0)$。其中 $cost(j + 1, i, c)$ 表示的是将区间 $[j + 1, i)$ 全部变为 $0$ 的代价,$c$ 为 $0$ 则没有附加操作代价,$c$ 为 $x$ 则表示需要整体反转 $i$ 和 $j$,代价为 $1$ 或 $x$。
- 求解 $cost(j + 1, i, c)$ 可以通过 $j$ 倒序枚举的过程逐步维护。
- 定义 $(c0, r0)$ 和 $(c1, r1)$ 两个二元组。$(c0, r0)$ 表示当第 $i$ 个位置为 $0$ 时 $[j + 1, i)$ 全部为 $0$ 的操作次数,以及第 $j$ 个位置是否会有附加的翻转。$(c1, r1)$ 同理。
- 按照以上定义,在移动 $j$ 的过程中,更新这两个二元组的值。$f$ 和 $g$ 的更新也可以根据这两个二元组的值来进行转移,具体可以参考代码。
时间复杂度
- 动态规划的状态数为 $O(n)$,转移时间为 $O(n)$,故总时间复杂度为 $O(n^2)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储状态。
拓展
- 此方法可以用于求解带限制条件或多种不同代价的操作,例如限制 $i$ 和 $j$ 的操作距离,或者不同的距离有不同的代价。
C++ 代码
class Solution {
public:
int minOperations(string s1, string s2, int x) {
const int INF = 1000000000;
const int n = s1.size();
vector<int> f(n, INF), g(n, INF);
if (s1[0] == s2[0]) f[0] = 0;
else g[0] = 0;
for (int i = 1; i < n; i++) {
int c0, c1;
bool r0, r1;
if (s1[i] == s2[i]) {
c0 = 0; r0 = false;
c1 = 1; r1 = true;
} else {
c0 = 1; r0 = true;
c1 = 0; r1 = false;
}
for (int j = i - 1; j >= 0; j--) {
f[i] = min(f[i], (r0 ? g[j] : f[j]) + c0);
f[i] = min(f[i], (r1 ? f[j] : g[j]) + c1 + (i - j == 1 ? 1 : x));
g[i] = min(g[i], (r0 ? f[j] : g[j]) + c0 + (i - j == 1 ? 1 : x));
g[i] = min(g[i], (r1 ? g[j] : f[j]) + c1);
if (s1[j] == s2[j]) {
if (r0) ++c0;
if (r1) ++c1;
} else {
if (r0) r0 = false;
else {
++c0;
r0 = true;
}
if (r1) r1 = false;
else {
++c1;
r1 = true;
}
}
}
}
return f[n - 1] == INF ? -1 : f[n - 1];
}
};
算法2
(贪心,动态规划) $O(n)$
- 先找到所有值不同位置的下标,如果总下标数为奇数,则直接返回 $-1$。
- 考虑下标对之间的匹配反转,对于下标 $i$ 和 $j$,可以直接通过 $x$ 的代价直接反转,也可以通过 $j - i$ 的代价移动反转。注意到,通过移动反转时,$i$ 和 $j$ 之间不存在其他下标对(否则可以拆成两组下标对使得代价变小)。
- 所以对于一个偶数个数的下标来说,可以和上一个位置的下标通过移动反转,也可以和前面一个没有匹配的下标直接反转。对于一个奇数个数的下标来说,可以和上一个位置的下标通过移动反转(保留前面某一个没有反转的下标),也可以作为一个新的没有反转的下标)。
- 至此,可以定义 $f$ 和 $g$,分别表示最近偶数位置下标的反转代价和最近奇数个数下标(有一个下标待反转)的最小代价。
- 如果当前下标个数为偶数,则 $f$ 可以转移 $f + i - prev$ 或 $g + x$,$g$ 保留无需转移。当前下标个数为奇数时,$g$ 可以转移 $g + i - prev$ 或 $f$,$f$ 无需转移。
时间复杂度
- 遍历字符串一次,故时间复杂度为 $O(n)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
int minOperations(string s1, string s2, int x) {
const int INF = 1000000000;
const int n = s1.size();
int prev = -1, cnt = 0;
int f = 0, g = INF;
for (int i = 0; i < n; i++) {
if (s1[i] == s2[i])
continue;
++cnt;
if (cnt % 2 == 0) f = min(f + i - prev, g + x);
else g = min(g + i - prev, f);
prev = i;
}
if (cnt % 2 == 1)
return -1;
return f;
}
};
二元组那里还是有点不清晰,我再看看👍