Leetcode 2896. Apply Operations to Make Two Strings Equal

本文主要是介绍Leetcode 2896. Apply Operations to Make Two Strings Equal，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Leetcode 2896. Apply Operations to Make Two Strings Equal
- 1. 解题思路
- 2. 代码实现

题目链接：2896. Apply Operations to Make Two Strings Equal

1. 解题思路

这一题的话我一开始的思路也是贪婪算法，不过遭遇了失败，所以后来还是暴力地使用了动态规划的处理方式。

显然，我们需要考虑的状态就只有两个：

临位是否有过翻转；
之前是否有过另一位翻转过；

此时，我们对于任意一位上的数值，只需要考虑如下几种情况：

如果两者相同
- 如果前一位没有翻转，那么这一位就不需要进行额外的操作，我们直接考虑下一位置即可；
- 如果前一位有过翻转，那么这一位事实上就是不同的，其对应的情况就是下述2中讨论的情况；
如果两者不同
- 如果前一位有过反转，那么这一位置上的数就也已经被翻转过了，我们就需要经过额外的操作了；
- 如果前一位并没有翻转，那么要使得这一位置上的数值相同，我们就需要在以下两个操作当中取最小值：
  - 按照操作2的方式翻转这个位置上的数以及其下个位置上的数，cost为1；
  - 按照操作1的方式翻转这个位置上的数，如果之前已经有过一次操作1了，那么此时我们不需要额外付出cost，反之我们需要付出的cost为x；

我们将其翻译为代码语言即可完成这道题目。

2. 代码实现

给出python代码实现如下：

class Solution:def minOperations(self, s1: str, s2: str, x: int) -> int:n = len(s1)@lru_cache(None)def dp(idx, flip, remain):if idx >= n:if not flip and remain == 0:return 0else:return math.infif s1[idx] == s2[idx]:if not flip:return dp(idx+1, False, remain)else:return min(1 + dp(idx+1, True, remain), x*(1-remain) + dp(idx+1, False, 1-remain))else:if flip:return dp(idx+1, False, remain)else:return min(1 + dp(idx+1, True, remain), x*(1-remain) + dp(idx+1, False, 1-remain))returnans = dp(0, False, 0)return ans if ans != math.inf else -1