LeetCode 1247. 交换字符使得字符串相同

Categories:

题目描述
思路分析
1. 解法一：统计错位对数（推荐）
相似题目

题目描述

✅ 1247. 交换字符使得字符串相同

思路分析

解法一：统计错位对数（推荐）

核心思路：

仅关注 s1[i] != s2[i] 的位置，分类为 xy 和 yx。

若 xy + yx 为奇数，无法配对返回 -1。

否则答案为 xy / 2 + yx / 2 + (xy % 2) * 2。

复杂度分析：

时间复杂度：O(n)，其中 n 为字符串长度。

空间复杂度：O(1)。

class Solution {
    public int minimumSwap(String s1, String s2) {
        int xy = 0;
        int yx = 0;
        for (int i = 0; i < s1.length(); i++) {
            char a = s1.charAt(i);
            char b = s2.charAt(i);
            if (a == b) {
                continue;
            }
            if (a == 'x') {
                xy++;
            } else {
                yx++;
            }
        }

        if ((xy + yx) % 2 == 1) {
            return -1;
        }

        return xy / 2 + yx / 2 + (xy % 2) * 2;
    }
}

func minimumSwap(s1 string, s2 string) int {
    xy := 0
    yx := 0
    for i := 0; i < len(s1); i++ {
        if s1[i] == s2[i] {
            continue
        }
        if s1[i] == 'x' {
            xy++
        } else {
            yx++
        }
    }

    if (xy+yx)%2 == 1 {
        return -1
    }

    return xy/2 + yx/2 + (xy%2)*2
}

相似题目

题目	难度	考察点
1790. 仅执行一次字符串交换能否使两个字符串相等	简单	字符串比较
859. 亲密字符串	简单	交换匹配
777. 在 LR 字符串中交换相邻字符	中等	贪心
1869. 哪种连续子字符串更长	简单	统计
1614. 括号的最大嵌套深度	简单	计数

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/25498924