题目如下:
解题思路:这个题目还是有点考巧劲的。如果s1[i] != s2[i],只有这两种取值 s1[i] = x,s2[i] = y(记为xy)和s1[i] = y,s2[i] = x(记为yx)。理想情况下,进行s1[i]和s2[j]的交换,使得s1[i] = s2[i] 与 s1[j] = s2[j]同时成立,那么一定是交换次数最少的场景。而题目中例子1的交换则符合这个场景,只要分别求出(xy)和(yx)的个数,然后分别进行(xy)和(yx)的组内交换,剩余的配对再进行例子2的组间交换,即可求得最小的交换次数。
代码如下:
class Solution(object): def minimumSwap(self, s1, s2): """ :type s1: str :type s2: str :rtype: int """ dic = {} dic[('x','y')] = 0 dic[('y','x')] = 0 for (i,j) in zip(s1,s2): if i != j: dic[(i,j)] += 1 if (dic[('x','y')] + dic[('y','x')] ) % 2 != 0: return -1 elif dic[('x','y')] % 2 == 0 and dic[('y','x')] % 2 == 0: return dic[('x','y')] / 2 + dic[('y','x')] / 2 return dic[('x','y')] / 2 + dic[('y','x')] / 2 + 2