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

2026-07-14 HGNULB 约 12 分钟

文章信息 3 个分类 4 个标签

分类

题目描述

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

题意分析

给定两个只含小写字母的字符串 word1 和 word2，问能否对 word1 反复施加两种操作，把它变成 word2。能变返回 true，不能返回 false。

两种操作必须一字一句读准，读错任何一处，整道题的判定条件就全错了。

操作一是交换任意两个现有字符的位置，例如 "abcde" 交换第二位和第五位得到 "aecdb"。它只动位置，字符本身一个都没变。

操作二是把某一个字符的所有出现全部变成另一个字符，同时把那个字符的所有出现全部变成前者，例如 "aacabb" 把 a 与 b 互换得到 "bbcbaa"。这里有两个约束特别容易漏：一是它是双向互换，不是单向替换，把所有 a 变成 b 的同时所有 b 必须变成 a，不存在「a 被 b 吞并、a 从此消失」这回事；二是参与互换的两个字符都必须是当前串里已经存在的，不能凭空引入一个原串中没有出现过的字母。

于是可以反推出哪些事情是做不到的：改变字符串长度做不到，因为两种操作都不增删字符；让某个字母彻底消失做不到，因为操作一不改变任何字母的出现次数，操作二把两个字母的出现次数对调、对调后两边仍然都是正数；变出一个新字母也做不到，理由同上。

把这三句话拧成不变量，就得到两条：

操作一只打乱顺序，每个字母的出现次数都原封不动，所以它既不改变出现过的字母组成的集合，也不改变各字母出现次数构成的多重集。

操作二不改变任何字母的「有没有出现」，只是把两个正的出现次数互相对调，所以它同样既不改变字母集合，也不改变出现次数的多重集——多重集里的数字一个没少，只是重新贴了标签。

两个操作都保住这两样东西，说明「字母集合相同」和「出现次数多重集相同」是能互相变换的必要条件。本题的关键结论是这两个条件合在一起也是充分的，即两者同时满足就一定能变过去。

约束里两串长度都在 $1$ 到 $10^5$ 之间，不必考虑空串；字符集固定为 26 个小写字母，这是个很强的信号，意味着与字母有关的那一维可以当成常数处理。需要单独照顾的边界有三个：两串长度本来就不相等（例如 "a" 与 "aa"），此时直接失败；两串完全相同，答案显然为 true；两串只有一个字符，只要相等就成立。

解法：计数数组加双条件判定

核心思路

上面已经论证了必要性：word1 与 word2 若能互变，则字母集合必须相同、出现次数的多重集必须相同。真正的难点在充分性——凭什么这两个条件一满足，就一定存在一串操作把 word1 变成 word2？

设两串共同的字母集合是 $S$，里面有 $k$ 个字母。把 word1 里这 $k$ 个字母的出现次数排成升序，把 word2 里的也排成升序，条件二说这两串数字逐位相同。于是可以定义一个 $S$ 到 $S$ 自身的映射：让「在 word1 中排第 $i$ 小的那个字母」对应「在 word2 中排第 $i$ 小的那个字母」。因为两边的字母集合都是同一个 $S$，这个映射的定义域和值域完全重合，它是 $S$ 上的一个置换。

这个置换正是我们要的重命名方案：把 word1 中每个字母按它改名，改完之后每个字母的出现次数就与 word2 里同名字母的出现次数逐个相等了。

剩下的问题是这次重命名能不能用操作二做出来。答案是能，因为任何置换都可以分解成若干次对换，也就是若干次「只把两个元素互相交换、其余不动」，而一次对换恰好就是操作二做的事。合法性也没有隐患：整个过程中被对换的两个字母始终属于 $S$，$S$ 里的字母出现次数从头到尾都是正数，永远满足「两个字符都必须已存在」这个前提。

举例说明。word1 = "aaabc" 的次数是 a 三次、b 一次、c 一次；word2 = "abccc" 的次数是 a 一次、b 一次、c 三次。置换只需把 a 与 c 对换，一次操作二就够："aaabc" 变成 "cccba"，此时 a 一次、b 一次、c 三次，与 word2 逐字母相等。若置换需要多于一次对换（比如三个字母首尾相接的轮换），就拆成两次操作二依次做，效果一样。

重命名结束后，两个串每个字母的出现次数完全一致，也就是说它们互为字母异位词，只差一个排列。这时操作一登场：反复交换两个位置可以把一个串重排成它任意一种排列，于是把顺序调成 word2 的样子即可。构造完成，充分性成立。

反过来看条件一为什么不能省。假如只要求出现次数的多重集相同，"abc" 和 "abd" 就会被判成接近：两边都是三个各出现一次的字母。但 word1 里根本没有 d，操作一不会造字母，操作二只在已有字母之间互换，d 永远变不出来，答案必须是 false。这说明两个条件互相独立，必须都查。

结论：word1 与 word2 接近，当且仅当两串出现过的字母集合完全相同，且两串各字母出现次数构成的多重集完全相同。长度相等是这两条的推论（多重集相同则次数之和相同），代码里仍然先判一次长度，用来提前退出并避免越界。

解题步骤

先比较两串长度，不相等直接返回 false。为什么：两种操作都不改变长度，长度不同必然失败；而且后面要用同一个下标同时遍历两个串，先卡住长度才不会读越界。

开两个长度 26 的计数数组，用一次遍历同时统计两个串。为什么用定长数组而不是哈希表：题目保证只有小写字母，c - 'a' 直接就是下标，常数更小，而且这个数组本身可以直接拿去排序，一物两用。

遍历下标 0 到 25，检查「这个字母在两边是否同为零、同为非零」，只要有一位一边是零另一边不是，立刻返回 false。为什么：这一步就是在比较两个字母集合，cnt[i] == 0 等价于「第 $i$ 个字母没出现过」。

这一步必须放在排序之前。为什么：排序会打乱下标与字母的对应关系，排完之后下标 $i$ 不再代表第 $i$ 个字母，「哪些字母出现过」的信息就永久丢失了。

把两个计数数组各自升序排序。为什么：操作二允许任意对调两个字母的出现次数，所以次数具体挂在哪个字母头上无关紧要，只有这 26 个数字组成的多重集有意义；排序是把多重集化成唯一的可比较形式。

逐位比较排序后的两个数组，全部相等返回 true，否则返回 false。为什么：这就是在判定两个多重集是否相同。

以 "cabbba" 与 "abbccc" 走一遍。先比长度，都是 6，通过。统计出 word1 的计数数组是 a 两次、b 三次、c 一次，其余 23 个字母全为零；word2 的计数数组是 a 一次、b 两次、c 三次，其余 23 个字母全为零。接着比字母集合：word1 出现过的是 {a, b, c}，word2 出现过的也是 {a, b, c}，26 个位置上「是否为零」逐位一致，通过。然后各自升序排序，word1 得到 23 个 0 后面跟着 1, 2, 3，word2 得到 23 个 0 后面跟着 1, 2, 3。逐位比较完全相同，返回 true。

这个 true 也可以手工兑现："cabbba" 先用操作二把 a 与 c 互换得到 "acbbbc"，再把 b 与 c 互换得到 "abcccb"，此时 a 一次、b 两次、c 三次，与 word2 逐字母相等；最后用操作一重排位置就得到 "abbccc"。

再看一个 false 用例 "abc" 与 "abd"，它专门卡「只判次数不判集合」的写法。长度都是 3，通过。word1 的计数是 a、b、c 各一次；word2 的计数是 a、b、d 各一次。走到字母集合检查时，下标 2（字母 c）上 word1 是 1 而 word2 是 0，一边非零一边为零，立刻返回 false。注意如果跳过这一步直接排序，两边都会得到 23 个 0 加 1, 1, 1，完全相等，函数会错答 true。

代码实现

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);
    }
}

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)$，$n$ 为字符串长度。统计计数遍历两串各一次，是 $O(n)$；字母集合检查固定循环 26 次；两次排序作用在长度 26 的定长数组上，$O(26 \log 26)$ 与输入规模无关，是常数。

空间复杂度：$O(1)$，只额外用了两个长度 26 的计数数组，容量由字符集大小决定，不随 $n$ 增长。

关键点总结

判断「某组操作能否把 A 变成 B」的通用套路是先找操作的不变量，再论证不变量全部相同就足以互相到达。不变量给出必要性，构造给出充分性，两头都讲到才算真正做完这道题。

证明充分性的标准手法是显式构造一条路径：先用一种操作把结构对齐（本题用对换把出现次数配到正确的字母上），再用另一种操作把顺序对齐。置换可以分解成若干次对换，是把「重命名」翻译成「一次次两两互换」的关键桥梁。

「出现次数具体挂在哪个键上」不重要而「这组次数本身」重要时，把计数数组排序就得到了多重集的规范形式；反过来若键与次数必须一一对应，就绝不能排序。判断一道计数题该不该排序，看的就是这个。

任何依赖「下标 $i$ 代表第 $i$ 个字母」的检查都必须在排序之前完成，排序会摧毁下标的语义，把检查悄悄变成恒真。

字母集合与出现次数多重集是两个互相推不出的独立条件："abc" 与 "abd" 次数多重集相同而字母集合不同，"aabb" 与 "abbb" 字母集合相同而次数多重集不同，两个反例各卡一半。

面试视角：面试官期望你先把两个操作的不变量说出来再写代码，也就是先讲「操作一保持每个字母的出现次数、操作二只对调两个次数」，从而推出要判哪两个条件，而不是上手就敲计数数组。常见追问是「为什么这两个条件是充要的」，必要性答不变量，充分性答置换分解成对换、再用操作一重排，最好能顺手给出一个只判次数不判集合就出错的反例。

易错点总结

只比较排序后的计数序列而不比较字母集合：喂 "abc" 与 "abd" → 两边排序后都是 23 个 0 加 1, 1, 1，函数返回 true，正确答案是 false。word1 里没有 d，两种操作都造不出新字母，这是本题最高频的错法。

忘记先判长度、两串共用一个下标遍历：喂 "aa" 与 "a" → Java 抛 StringIndexOutOfBoundsException: String index out of range: 1，Go 直接 panic: runtime error: index out of range [1] with length 1；把参数顺序换成 "a" 与 "aa" 更阴险，不崩溃，但循环只走 1 次、只统计到 word2 的第一个字符，两边都得到 a 一次，返回 true，正确答案是 false。

只比较字母集合而不比较出现次数的多重集：喂 "aabb" 与 "abbb" → 两边字母集合都是 {a, b}，函数返回 true，正确答案是 false。这种写法在 "a" 与 "aa" 上侥幸答对，只因为长度判断先把它拦下了，别被这种假通过骗过去。

直接逐位比较未排序的计数数组，把本题当成字母异位词：喂 "cabbba" 与 "abbccc" → 下标 0 上 word1 是 2 而 word2 是 1，函数返回 false，正确答案是 true。这等于完全忽略了操作二，把题目退化成了 242 题。

只排序其中一个计数数组：喂 "cabbba" 与 "abbccc" → 排好序的 word1 是 23 个 0 加 1, 2, 3，没排序的 word2 是 1, 2, 3 加 23 个 0，逐位一比就不等，返回 false，正确答案是 true。

字母集合条件写成「两边都必须非零」，即 if (cnt1[i] == 0 || cnt2[i] == 0) return false：喂 "abc" 与 "bca" → 循环走到下标 3（字母 d）时两边都是 0，条件成立，返回 false，正确答案是 true。这种写法实际是在要求 26 个字母全部出现，除极少数输入外恒答 false。正确的写法是判两边「是否为零」这件事是否一致，用 (cnt1[i] == 0) != (cnt2[i] == 0)。

把字母集合检查放到排序之后：喂 "abc" 与 "abd" → 排序后两边的 0 全被推到数组前段、非零值全在后段，零的位置自动对齐，检查一位都不会触发，函数返回 true，正确答案是 false。这个错误比忘记检查更难查，因为代码里那段检查明明写着，只是已经失效了。

只把非零计数收集成列表再排序比较：喂 "abc" 与 "abd" → 两边收集出的列表都是 [1, 1, 1]，返回 true，正确答案是 false。剔掉 0 的同时也把「哪些字母出现过」的信息一起剔掉了，效果等同于第一条。

Java 里用 == 比较两个 int[]：喂 "abc" 与 "bca" → a == b 比较的是两个数组的引用，两个 new int[26] 永远不是同一个对象，返回 false，正确答案是 true；这种写法对任何输入都只会答 false。比较数组内容必须用 Arrays.equals。

Go 里把 [26]int 直接传给 sort.Ints：编译期就报 cannot use cnt1 (variable of type [26]int) as []int value in argument to sort.Ints，必须写 sort.Ints(cnt1[:]) 取全切片；但反过来若把计数容器改成 make([]int, 26) 这样的切片，最后又不能用 == 比较，编译报 invalid operation: cnt1 == cnt2 (slice can only be compared to nil)，得换成 slices.Equal 或 reflect.DeepEqual。用定长数组配 cnt[:] 排序、再用 == 比内容，是这道题最省事的组合。

相似题目

题目	难度	考察点
242. 有效的字母异位词	简单	同样开 26 计数数组，但要求逐字母计数相等，不允许把次数在字母之间搬动，是本题去掉操作二后的退化情形
49. 字母异位词分组	中等	把异位词判定升级成批量分组，重点是为每个串造一个可作哈希键的签名，而本题只需一次两串比较
383. 赎金信	简单	比较两组计数时要的是单向覆盖「每个字母够用即可」，判据是不等式而不是本题的等式
451. 根据字符出现频率排序	中等	统计完次数后要按次数降序把字符串重新拼出来，关心次数的排名与结果重构，而非两串次数分布是否一致
1207. 独一无二的出现次数	简单	只看一个数组内部的次数多重集是否元素互不相同，本题看两个字符串的次数多重集是否彼此相同
2215. 找出两数组的不同	简单	只做存在性差集、完全不管出现次数，恰好是本题两个条件里被单独剥出来的那一半