LeetCode 1657. 确定两个字符串是否接近

约 5 分钟
文章信息 3 个分类 4 个标签
分类
LeetCode 中等 LeetCode 75
标签
字符串 哈希表 排序 计数

题目描述

✅ 1657. 确定两个字符串是否接近

image-20260928234232201

image-20260928234232204

题意分析

判断能否通过两种操作把 word1 变成 word2：一是交换任意两个位置上的字符，二是选两个已经存在的字符，把它们的所有出现同时互换。两种操作都可以执行任意多次。

第一种只调整位置，第二种交换的是两个字符的完整身份，不能只替换其中一次，也不能引入原来没有的字符。本题不要求给出操作过程，只判断两个字符串是否满足可互相转换的条件。

解法：字符集合相同且频次多重集合相同

核心思路

[!blue]

先看两种操作保留了什么。交换位置不会改变任何字符的出现次数；交换两种已有字符的全部出现，会把这两种字符的次数互换，却不会改变已经出现的字符种类，也不会改变所有次数组成的多重集合。字符串总长度同样不会变化。

因此，两个字符串必须具有相同的出现字符集合；同时，不关心次数具体属于哪个字符时，两边的频次列表必须能一一对应。这里是多重集合，相同的次数出现了多少遍也要相同，不能去重后只比较有哪些次数。

这两个条件不仅必要，也足够。频次多重集合相同，可以把已有字符的身份重新对应，使每个目标字符获得它需要的次数；任意这样的身份排列都能拆成若干次两字符全局交换。字符集合相同保证需要交换的身份始终都是已有字符。次数对齐后，再通过任意位置交换，就能将字符排列成目标字符串。

代码使用 26 项数组按字母统计频次。先按同一个字母下标检查两边是否同时为零，判断出现集合一致；再分别排序两张频次数组，比较次数多重集合。顺序不能反过来，因为排序之后，下标就不再对应原字母，无法继续判断某个具体字母是否出现。

开始时先排除长度不同的情况，也保证后面的共用下标扫描安全。检查全部通过，就无需模拟任何一次真实交换。

解题步骤

  1. 两个字符串长度不同，直接返回假。
  2. 统计每个小写字母在两串中的次数。
  3. 逐字母比较是否出现，只要一边为零、另一边非零就返回假。
  4. 分别排序两张计数数组，逐项相等则返回真，否则返回假。

代码实现

class Solution {
    public boolean closeStrings(String word1, String word2) {
        // 两种操作都不改变长度，长度不等必然失败，也顺便保证下面共用下标不越界。
        if (word1.length() != word2.length()) {
            return false;
        }

        int[] cnt1 = new int[26];
        int[] cnt2 = new int[26];

        for (int i = 0; i < word1.length(); i++) {
            // 只含小写字母，减去 'a' 直接当下标。
            cnt1[word1.charAt(i) - 'a']++;
            cnt2[word2.charAt(i) - 'a']++;
        }

        for (int i = 0; i < 26; i++) {
            // 条件一：字母集合必须相同。必须在排序之前判，排序会毁掉下标与字母的对应。
            if ((cnt1[i] == 0) != (cnt2[i] == 0)) {
                return false;
            }
        }

        // 条件二：出现次数的多重集相同，排序后逐位比较即可。
        Arrays.sort(cnt1);
        Arrays.sort(cnt2);

        // int[] 必须用 Arrays.equals 比较内容，== 比的是引用。
        return Arrays.equals(cnt1, cnt2);
    }
}

import (
    "sort"
)

func closeStrings(word1 string, word2 string) bool {
    // 两种操作都不改变长度，长度不等必然失败，也顺便保证下面共用下标不越界。
    if len(word1) != len(word2) {
        return false
    }

    var cnt1, cnt2 [26]int

    for i := 0; i < len(word1); i++ {
        // 字符串按字节索引，只含小写字母时减去 'a' 就是下标。
        cnt1[word1[i]-'a']++
        cnt2[word2[i]-'a']++
    }

    for i := 0; i < 26; i++ {
        // 条件一：字母集合必须相同。必须在排序之前判。
        if (cnt1[i] == 0) != (cnt2[i] == 0) {
            return false
        }
    }

    // 条件二：出现次数的多重集相同。sort.Ints 收切片，数组要用 cnt1[:] 取全切片。
    sort.Ints(cnt1[:])
    sort.Ints(cnt2[:])

    // 定长数组是可比较类型，== 直接逐元素比较内容。
    return cnt1 == cnt2
}

复杂度分析

  • 时间复杂度：$O(n+26\log26)$，其中 n 为等长时的字符串长度。字母表固定，计数排序视为常量开销，整体为 $O(n)$。
  • 空间复杂度：$O(1)$，两张频次数组大小固定，不随字符串长度增长。

关键点总结

[!green]

  • 出现集合限制允许使用哪些字符身份，频次多重集合限制这些身份可以分配到哪些数量。
  • 两条件满足时，先通过全局互换配齐次数，再通过位置交换还原目标顺序，给出了可行转换的依据。
  • 先检查字母身份，再排序次数，避免丢失下标与字符的对应关系。

易错点总结

[!yellow]

  • 只比较排序后的次数，可能接受使用了不同字符集合的两个字符串，已有字符互换无法创造新字符。
  • 要求每个具体字符的原频次完全相同，会忽略题目允许全局交换字符身份，条件过强。
  • 先排序计数再检查每个字母是否出现，已经无法知道原计数属于哪个字母。
  • 用去重集合保存次数，会丢掉同一个次数对应了多少种字符的信息。
  • 将第二种操作理解成只替换单个字符，会错误认为能够任意改变频次数量。

相似题目

题目 难度 关联与区别
242. 有效的字母异位词 简单 原题只允许位置重排，每种字符频次必须相同；本题还能全局互换已有字符身份。
1207. 独一无二的出现次数 简单 同样把出现次数单独作为数据，本题比较频次多重集合，原题检查次数是否互异。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/53703646
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！