泡LeetCode的日子-交换字符使得字符串相同

题目

题解

将两个输入的等长字符串转为字符数组, 则在对应0 <= index < s1.length()的index中, xy表示两个字符数组相同位置x<->y的对数, yx表示y<->x的对数, 有如下三种可能:

  1. 两个字符数组对应位置都为x或者都为y, 则不需要交换, ans = 0;
  2. 两个字符数组对应位置为x<->y或者y<->x, 则又有以下两种情况:
    • 首先, x<->y与x<->y交换位置, 只需要交换一次即可成为x<->x/y<->y, y<->x与y<->x同理. 则ans = ans + xy/2 + yx/2
    • 其次, 剩下的就只有x<->y和y<->x了, 这里也有三种情况:
      • x<->y和y<->x各一个, 则需要两次交换才能成为x<->x/y<->y, ans += 2(等价于ans = ans + xy%2 +yx%2);
      • x<->y和y<->x都没有, 则ans不变
      • x<->y和y<->x只有其中一对有一个, 则无法交换, ans = -1
public int minimumSwap(String s1, String s2) {
    char[] chars1 = s1.toCharArray();
    char[] chars2 = s2.toCharArray();

    int xy = 0;
    int yx = 0;

    for (int i = 0; i < s1.length(); i++) {
        if (chars1[i] == chars2[i]) {
            continue;
        } else if (chars1[i] == 'x') {
            xy++;
        } else {
            yx++;
        }
    }
    // 如果为xy<->xy或者yx<->yx, 则需要一次交换即可
    int ans = xy / 2 + yx / 2;
    // 剩下的xy<->yx则需要两次交换才可以, 如果xy<->yx等于0, 则不需要交换即xy+yx=0
    // 否则, xy<->yx各一对, 则需要交换两次, 即xy+yx=2
    // 如果, xy<->yx只有其中一对, 则无法组合, 返回-1
    xy %= 2;
    yx %= 2;
    return (xy + yx) == 1 ? -1 : ans + xy + yx;
}
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容