Minimum Swaps to Make Strings Equal
给两个x和y组成的字符串, 问这两个字符串最少通过swap后, 能相同. 这个题有点巧妙, 我一开始以为是dp, 因为求optimization.不过看了例子后, 感觉是简单的逻辑题. 首先要看两个string的不同的位置有几个. 如果是奇数肯定不行, 因为要swap. 其次通过给出的两个例子, 已经知道如果是奇数x和y, 那么要n/2+1次, 如果x和y正好相同, 则只需要n/2次. 再多写几个例子, 发现只有这三种可能.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
class Solution { public int minimumSwap(String s1, String s2) { int diff = 0; int numsX = 0; int n = s1.length(); for(int i = 0; i < n; i ++) { if(s1.charAt(i) == s2.charAt(i)) { continue; } diff++; if(s1.charAt(i) == 'x') { numsX++; } } if(diff % 2 != 0) // swaping needs at least 2 diffs return -1; if(numsX % 2 == 0) { //if it is in case 1 return diff / 2; } else { return (diff / 2) + 1; } } } |