LeetCode 1657中等哈希/字符串
确定两个字符串是否接近 图解题解
这道题到底在问什么
允许两种操作:① 任意重排字符 ② 把两个已有字符的名字整体互换(交换标签)。问 word1 能否变成 word2。
- 输入
- word1="cabbba", word2="abbccc"
- 输出
- true
- 输入
- word1="a", word2="aa"
- 输出
- false（长度不同）
最优解：一步一步想明白
- 3记住「① 字符集合相同 ② 出现次数多重集相同」,两条都过才接近。下面先各自计数,再逐条核对。
- 4第一步:数清 word1 里每种字符出现几次。从左到右扫,每个字符给它的计数加一。
- 5word1 第 0 个字符是 'c'，把它的计数加到 1（高亮行）。
- 6word1 第 1 个字符是 'a'，把它的计数加到 1（高亮行）。
- 7word1 第 2 个字符是 'b'，把它的计数加到 1（高亮行）。
- 8word1 第 3 个字符是 'b'，把它的计数加到 2（高亮行）。
- 9word1 第 4 个字符是 'b'，把它的计数加到 3（高亮行）。
- 10word1 第 5 个字符是 'a'，把它的计数加到 2（高亮行）。
- 11第二步:同样数清 word2 里每种字符的次数。注意舞台上的数组已切换成 word2。
- 12word2 第 0 个字符是 'a'，把它的计数加到 1（高亮行）。
- 13word2 第 1 个字符是 'b'，把它的计数加到 1（高亮行）。
- 14word2 第 2 个字符是 'b'，把它的计数加到 2（高亮行）。
- 15word2 第 3 个字符是 'c'，把它的计数加到 1（高亮行）。
- 16word2 第 4 个字符是 'c'，把它的计数加到 2（高亮行）。
- 17word2 第 5 个字符是 'c'，把它的计数加到 3（高亮行）。
- 18条件①核对字符 'a'：word1 有、word2 有，一致（绿色）。
- 19条件①核对字符 'b'：word1 有、word2 有，一致（绿色）。
- 20条件①核对字符 'c'：word1 有、word2 有，一致（绿色）。
- 21条件①整体判定:两边用到的字符集合完全相同，第一关通过。
- 22条件②看「次数的多重集」。先把 word1 各字符的次数列出来 [1,2,3]，排序成 [1,2,3]。
- 23再把 word2 各字符的次数列出来 [1,2,3]，排序成 [1,2,3]。
- 24比较两个排序后的次数列:[1,2,3] 完全相等，第二关也通过。
- 25综合:长度相同、条件①满足、条件②满足，所以两字符串接近，返回 true。
⚠️ 容易写错的地方
✗ 错：只比较两个计数数组是否完全相等
✓ 对：要分两条:集合相同 + 排序后相同
交换名字能在已有字符间重新分配频次,所以不要求同一字母次数相同,只要多重集相同
✗ 错：忘了先判长度
✓ 对：长度不同直接返回 false
长度不同绝不可能接近,先挡掉省事
✗ 错：以为「次数多重集相同」就够
✓ 对：还得「字符集合相同」
如 "aaa" 与 "bbb" 次数多重集都是 [3],但字符集合不同,不接近
完整代码（Python / C++ / Java）
Python
class Solution:
def closeStrings(self, word1: str, word2: str) -> bool:
if len(word1) != len(word2):
return False
a = [0] * 26
b = [0] * 26
for ch in word1:
a[ord(ch) - 97] += 1
for ch in word2:
b[ord(ch) - 97] += 1
return [x > 0 for x in a] == [x > 0 for x in b] and sorted(a) == sorted(b)C++
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
bool closeStrings(string word1, string word2) {
if (word1.size() != word2.size()) return false;
vector<int> a(26), b(26);
for (char c : word1) a[c - 'a']++;
for (char c : word2) b[c - 'a']++;
for (int i = 0; i < 26; ++i) if ((a[i] == 0) != (b[i] == 0)) return false;
sort(a.begin(), a.end()); sort(b.begin(), b.end());
return a == b;
}
};Java
import java.util.*;
class Solution {
public boolean closeStrings(String word1, String word2) {
if (word1.length() != word2.length()) return false;
int[] a = new int[26], b = new int[26];
for (char c : word1.toCharArray()) a[c - 'a']++;
for (char c : word2.toCharArray()) b[c - 'a']++;
for (int i = 0; i < 26; i++) if ((a[i] == 0) != (b[i] == 0)) return false;
Arrays.sort(a); Arrays.sort(b);
return Arrays.equals(a, b);
}
}复杂度
时间
O(n + Σ logΣ)
计数 O(n);排序固定 26 个计数,排序项是常数
空间
O(1)
两个长度 26 的计数数组,与 n 无关
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 确定两个字符串是否接近 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
两个条件分别对应哪种操作?+
条件②(次数多重集相同)对应「重排 + 在已有字符间交换名字、重新分配频次」;条件①(字符集合相同)保证「交换只在已有字符之间,不新增不消灭字符种类」。两者合起来恰好刻画了允许的全部操作。
能否用一个 26 长数组同时判两条?+
可以:统计 a、b 两个计数数组;条件①逐位比较 (a[i]==0)==(b[i]==0);条件②对 a、b 排序后比较相等。固定 26,排序是常数开销,整体 O(n)。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 确定两个字符串是否接近 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。