LeetCode 题解工作台
执行操作使两个字符串相等
给你两个下标从 0 开始的二进制字符串 s1 和 s2 ，两个字符串的长度都是 n ，再给你一个正整数 x 。 你可以对字符串 s1 执行以下操作 任意次 ： 选择两个下标 i 和 j ，将 s1[i] 和 s1[j] 都反转，操作的代价为 x 。 选择满足 i 的下标 i ，反转 s1[i] 和 …
2
题型
5
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
我们注意到，由于每次操作都是反转两个字符，因此，如果不同的字符个数为奇数，那么无法使两个字符串相等，直接返回 。否则，我们将两个字符串中不同的字符的下标存入数组 中，记数组长度为 。 接下来，我们设计一个函数 $dfs(i, j)$，表示将 中的字符反转的最小操作代价。答案即为 $dfs(0, m - 1)$。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你两个下标从 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'。
解题思路
方法一：记忆化搜索
我们注意到，由于每次操作都是反转两个字符，因此，如果不同的字符个数为奇数，那么无法使两个字符串相等，直接返回 。否则，我们将两个字符串中不同的字符的下标存入数组 中，记数组长度为 。
接下来，我们设计一个函数 ，表示将 中的字符反转的最小操作代价。答案即为 。
函数 的计算过程如下：
如果 ，那么不需要进行任何操作，返回 ；
否则，我们考虑对区间 的端点进行操作：
- 如果我们对端点 进行第一种操作，由于代价 已经固定，因此，我们最优的选择是将 和 反转，然后递归计算 ，总代价为 ；
- 如果我们对端点 进行第二种操作，那么我们需要将 中的字符全部反转，然后递归计算 ，总代价为 ；
- 如果我们对端点 进行第二种操作，那么我们需要将 中的字符全部反转，然后递归计算 ，总代价为 。
我们取上述三种操作的最小值，即为 的值。
为了避免重复计算，我们可以使用记忆化搜索。
时间复杂度 ，空间复杂度 。其中 是字符串的长度。
class Solution:
def minOperations(self, s1: str, s2: str, x: int) -> int:
@cache
def dfs(i: int, j: int) -> int:
if i > j:
return 0
a = dfs(i + 1, j - 1) + x
b = dfs(i + 2, j) + idx[i + 1] - idx[i]
c = dfs(i, j - 2) + idx[j] - idx[j - 1]
return min(a, b, c)
n = len(s1)
idx = [i for i in range(n) if s1[i] != s2[i]]
m = len(idx)
if m & 1:
return -1
return dfs(0, m - 1)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for an understanding of dynamic programming and state transitions.
- question_mark
Check the candidate's ability to reduce problem complexity by focusing on mismatched positions.
- question_mark
Evaluate how efficiently the candidate applies operations to minimize transformation cost.
常见陷阱
外企场景- error
Failing to focus on mismatched positions, leading to inefficient solutions.
- error
Misapplying the flipping operation when it's not cost-effective.
- error
Overcomplicating the problem by not leveraging dynamic programming.
进阶变体
外企场景- arrow_right_alt
What if the strings are of different lengths?
- arrow_right_alt
How can you optimize the approach for larger values of x?
- arrow_right_alt
How does this problem relate to other dynamic programming challenges?