1247. 交换字符使得字符串相同 #
- 标签:贪心、数学、字符串
- 难度:中等
题目大意 #
描述:给定两个长度相同的字符串 s1
和 s2
,并且两个字符串中只含有字符 'x'
和 'y'
。现在需要通过「交换字符」的方式使两个字符串相同。
- 每次「交换字符」,需要分别从两个字符串中各选一个字符进行交换。
- 「交换字符」只能发生在两个不同的字符串之间,不能发生在同一个字符串内部。
要求:返回使 s1
和 s2
相同的最小交换次数,如果没有方法能够使得这两个字符串相同,则返回 -1
。
说明:
- $1 \le s1.length, s2.length \le 1000$。
s1
、s2
只包含'x'
或'y'
。
示例:
- 示例 1:
|
|
解题思路 #
思路 1:贪心算法 #
- 如果
s1 == 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] == 'x'
,s2[i] == 'y'
时,则统计数量到变量xyCnt
中。 - 当遇到
s1[i] == 'y'
,s2[i] == 'y'
时,则统计数量到变量yxCnt
中。
则最后我们只需要判断 xyCnt
和 yxCnt
的个数即可。
- 如果
xyCnt + yxCnt
是奇数,则说明最终会有一个位置上的两个字符无法通过交换相匹配。 - 如果
xyCnt + yxCnt
是偶数,并且xyCnt
为偶数,则yxCnt
也为偶数。则优先交换"xx"
与"yy"
、"yy"
与"xx"
。即每两个xyCnt
对应一次交换,每两个yxCnt
对应交换一次,则结果为xyCnt // 2 + yxCnt // 2
。 - 如果
xyCnt + yxCnt
是偶数,并且xyCnt
为奇数,则yxCnt
也为奇数。则优先交换"xx"
与"yy"
、"yy"
与"xx"
。即每两个xyCnt
对应一次交换,每两个yxCnt
对应交换一次,则结果为xyCnt // 2 + yxCnt // 2
。最后还剩一组"xy"
与"yx"
或者"yx"
与"xy"
,则再交换一次,则结果为xyCnt // 2 + yxCnt // 2 + 2
。
以上结果可以统一写成 xyCnt // 2 + yxCnt // 2 + xyCnt % 2 * 2
。
思路 1:贪心算法代码 #
|
|