【每日一题Day129】LC1247交换字符使得字符串相同 | 贪心

交换字符使得字符串相同【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

  交换的方法有两种

  1. 通过一次交换（x<->y 或者y<->x ）使nXy或者nYx减少2
  2. 通过两次交换（x<->x x<->y 或者y<->y y<->x）使nXy和nYx各减少1

  如果nXy和nYx有一个为奇数，那么无法使字符串相等。否则优先采取第一种交换方式【局部最优】，然后当都只剩下一个时，通过两次交换使字符串相等，交换次数为$nXy/2+nYx/2+nXy\%2+nYx\%2$

• 实现

  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)$