Minimum Swaps to Make Strings Equal
给两个x和y组成的字符串, 问这两个字符串最少通过swap后, 能相同. 这个题有点巧妙, 我一开始以为是dp, 因为求optimization.不过看了例子后, 感觉是简单的逻辑题. 首先要看两个string的不同的位置有几个. 如果是奇数肯定不行, 因为要swap. 其次通过给出的两个例子, 已经知道如果是奇数x和y, 那么要n/2+1次, 如果x和y正好相同, 则只需要n/2次. 再多写几个例子, 发现只有这三种可能.
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;
}
}
}