跳至主要內容

1247. 交换字符使得字符串相同

ITCharge大约 3 分钟

1247. 交换字符使得字符串相同open in new window

  • 标签:贪心、数学、字符串
  • 难度:中等

题目链接

题目大意

描述:给定两个长度相同的字符串 s1s1s2s2,并且两个字符串中只含有字符 'x''y'。现在需要通过「交换字符」的方式使两个字符串相同。

  • 每次「交换字符」,需要分别从两个字符串中各选一个字符进行交换。
  • 「交换字符」只能发生在两个不同的字符串之间,不能发生在同一个字符串内部。

要求:返回使 s1s1s2s2 相同的最小交换次数,如果没有方法能够使得这两个字符串相同,则返回 1-1

说明

  • 1s1.length,s2.length10001 \le s1.length, s2.length \le 1000
  • s1s1、$ s2$ 只包含 'x''y'

示例

  • 示例 1:
输入:s1 = "xy", s2 = "yx"
输出:2
解释:
交换 s1[0] 和 s2[0],得到 s1 = "yy",s2 = "xx" 。
交换 s1[0] 和 s2[1],得到 s1 = "xy",s2 = "xy" 。
注意,你不能交换 s1[0] 和 s1[1] 使得 s1 变成 "yx",因为我们只能交换属于两个不同字符串的字符。

解题思路

思路 1:贪心算法

  • 如果 s1==s2s1 == s2,则不需要交换。
  • 如果 s1 = "xx"s2 = "yy",则最少需要交换一次,才可以使两个字符串相等。
  • 如果 s1 = "yy"s2 = "xx",则最少需要交换一次,才可以使两个字符串相等。
  • 如果 s1 = "xy"s2 = "yx",则最少需要交换两次,才可以使两个字符串相等。
  • 如果 s1 = "yx"s2 = "xy",则最少需要交换两次,才可以使两个字符串相等。

则可以总结为:

  • "xx""yy""yy""xx" 只需要交换一次。
  • "xy""yx""yx""xy" 需要交换两次。

我们把这两种情况分别进行统计。

  • 当遇到 s1[i]==s2[i]s1[i] == s2[i] 时直接跳过。
  • 当遇到 s1[i] == 'x's2[i] == 'y' 时,则统计数量到变量 xyCntxyCnt 中。
  • 当遇到 s1[i] == 'y's2[i] == 'y' 时,则统计数量到变量 yxCntyxCnt 中。

则最后我们只需要判断 xyCntxyCntyxCntyxCnt 的个数即可。

  • 如果 xyCnt+yxCntxyCnt + yxCnt 是奇数,则说明最终会有一个位置上的两个字符无法通过交换相匹配。
  • 如果 xyCnt+yxCntxyCnt + yxCnt 是偶数,并且 xyCntxyCnt 为偶数,则 yxCntyxCnt 也为偶数。则优先交换 "xx""yy""yy""xx"。即每两个 xyCntxyCnt 对应一次交换,每两个 yxCntyxCnt 对应交换一次,则结果为 xyCnt÷2+yxCnt÷2xyCnt \div 2 + yxCnt \div 2
  • 如果 xyCnt+yxCntxyCnt + yxCnt 是偶数,并且 xyCntxyCnt 为奇数,则 yxCntyxCnt 也为奇数。则优先交换 "xx""yy""yy""xx"。即每两个 xyCntxyCnt 对应一次交换,每两个 yxCntyxCnt 对应交换一次,则结果为 xyCnt÷2+yxCnt÷2xyCnt \div 2 + yxCnt \div 2。最后还剩一组 "xy""yx" 或者 "yx""xy",则再交换一次,则结果为 xyCnt÷2+yxCnt÷2+2xyCnt \div 2 + yxCnt \div 2 + 2

以上结果可以统一写成 xyCnt÷2+yxCnt÷2+xyCntmod2×2xyCnt \div 2 + yxCnt \div 2 + xyCnt \mod 2 \times 2

思路 1:贪心算法代码

class Solution:
    def minimumSwap(self, s1: str, s2: str) -> int:
        xyCnt, yxCnt = 0, 0
        for i in range(len(s1)):
            if s1[i] == s2[i]:
                continue
            if s1[i] == 'x':
                xyCnt += 1
            else:
                yxCnt += 1

        if (xyCnt + yxCnt) & 1:
            return -1
        return xyCnt // 2 + yxCnt // 2 + (xyCnt % 2 * 2)

思路 1:复杂度分析

  • 时间复杂度O(n)O(n),其中 nn 为字符串的长度。
  • 空间复杂度O(1)O(1)