交换字符使得字符串相同【LC1247】
有两个长度相同的字符串
s1和s2，且它们其中 只含有 字符"x"和"y"，你需要通过「交换字符」的方式使这两个字符串相同。每次「交换字符」的时候，你都可以在两个字符串中各选一个字符进行交换。
交换只能发生在两个不同的字符串之间，绝对不能发生在同一个字符串内部。也就是说，我们可以交换
s1[i]和s2[j]，但不能交换s1[i]和s1[j]。最后，请你返回使
s1和s2相同的最小交换次数，如果没有方法能够使得这两个字符串相同，则返回-1。
考完一门 下周还有一门 加油哇
- 思路
当两种字符串某个位置字符不同时，有两种情况:
- 第一种情况为
s1[i]为x，s2[i]为y，记该种情况次数为nXy - 第二种情况为
s1[i]为y，s2[i]为X，记该种情况次数为nYx
交换的方法有两种
- 通过一次交换（x<->y 或者y<->x ）使
nXy或者nYx减少2 - 通过两次交换（x<->x x<->y 或者y<->y y<->x）使
nXy和nYx各减少1
实现
class Solution { public int minimumSwap(String s1, String s2) { int nX = 0, nY = 0; int n = s1.length(); for (int i = 0; i < n; i++){ if (s1.charAt(i) != s2.charAt(i)){ if (s1.charAt(i) == 'x'){ nX++; }else{ nY++; } } } int res = 0; res += nX / 2; if (nX % 2 == 1){ res += 1; nY++; } if (nY % 2 == 1){ return -1; } res += nY / 2; return res; } }
复杂度
- 时间复杂度：O ( n )
- 空间复杂度：O ( 1 )
