1. 概述
根据 Wikipedia 的定义，变位词（anagram） 是指通过重新排列一个单词或短语的字母，形成另一个单词或短语。
我们可以把这个概念扩展到字符串处理中：如果两个字符串包含完全相同的字符及其出现次数，只是顺序不同，那么它们互为变位词。
本文将探讨如何判断两个字符串是否为全字符匹配的变位词 —— 包括空格、标点、数字等非字母字符。例如，"!low-salt!" 和 "owls-lat!!" 就是变位词，因为它们包含完全相同的字符和频次。
✅ 目标：判断两字符串是否互为变位词（字符频次完全一致）
❌ 不是：仅字母重排、忽略大小写或符号（除非特别处理）
2. 解法概览
我们来对比几种判断变位词的常见方法。所有方案都会先做一步快速校验：
⚠️ 如果两个字符串长度不同，直接返回
false—— 长度不等不可能是变位词。
我们会从两个维度评估每种方案：
- ✅ 开发复杂度：代码是否简洁、易维护
- ⚙️ 时间复杂度：使用大 O 表示法分析性能
3. 排序法判断变位词
思路很简单：对两个字符串的字符排序，若结果相同，则为变位词。
Java 实现步骤：
- 转为
char[] - 使用
Arrays.sort()排序 - 用
Arrays.equals()判断是否相等
boolean isAnagramSort(String string1, String string2) {
if (string1.length() != string2.length()) {
return false;
}
char[] a1 = string1.toCharArray();
char[] a2 = string2.toCharArray();
Arrays.sort(a1);
Arrays.sort(a2);
return Arrays.equals(a1, a2);
}
优缺点分析
- ✅ 实现简单直观，适合快速编码
- ⚠️ 时间复杂度为 **O(n log n)**，瓶颈在排序
- 💾 需要额外空间存储两个字符数组
👉 适合对性能要求不高、追求可读性的场景。简单粗暴，但不是最优解。
4. 计数法（字符频次统计）
核心思想：统计每个字符出现次数，若两字符串的“字符频次直方图”一致，则为变位词。
优化技巧：只用一个计数数组：
- 遍历第一个字符串：字符计数
++ - 遍历第二个字符串：字符计数
-- - 最终所有计数应为 0，否则不是变位词
假设字符集为 ASCII（0~255），可用长度为 256 的数组：
private static int CHARACTER_RANGE = 256;
public boolean isAnagramCounting(String string1, String string2) {
if (string1.length() != string2.length()) {
return false;
}
int count[] = new int[CHARACTER_RANGE];
for (int i = 0; i < string1.length(); i++) {
count[string1.charAt(i)]++;
count[string2.charAt(i)]--;
}
for (int i = 0; i < CHARACTER_RANGE; i++) {
if (count[i] != 0) {
return false;
}
}
return true;
}
优缺点分析
- ✅ 时间复杂度为 **O(n)**，性能优秀
- 💾 空间复杂度固定为 O(256)，对 ASCII 来说可以接受
- ⚠️ 若扩展到 UTF-8（如中文），
CHARACTER_RANGE会剧增，内存开销大 - ❌ 代码略繁琐，依赖手动管理数组
👉 适合字符集有限、追求极致性能的场景，比如处理大量英文文本。
5. 使用 Guava 的 MultiSet
想避免手动计数？可以用 Guava 提供的 Multiset —— 支持重复元素、顺序无关的集合。
✅
{a, a, b}和{b, a, a}被认为是相等的 Multiset
引入依赖
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>31.0.1-jre</version>
</dependency>
实现代码
boolean isAnagramMultiset(String string1, String string2) {
if (string1.length() != string2.length()) {
return false;
}
Multiset<Character> multiset1 = HashMultiset.create();
Multiset<Character> multiset2 = HashMultiset.create();
for (int i = 0; i < string1.length(); i++) {
multiset1.add(string1.charAt(i));
multiset2.add(string2.charAt(i));
}
return multiset1.equals(multiset2);
}
优缺点分析
- ✅ 时间复杂度 **O(n)**，性能好
- ✅ 不需要预设字符范围，自动扩容，适合 Unicode
- ✅ 利用高级集合类，代码更简洁、可读性强
- ⚠️ 引入第三方依赖（Guava），增加项目复杂度
👉 推荐在已使用 Guava 的项目中使用，开发效率高，不易踩坑。
6. 字母级变位词（忽略大小写与符号）
前面的例子是“全字符匹配”，但实际语言中，我们更关心字母重排，比如：
“A decimal point” ↔ “I’m a dot in place.”
这种情况下，我们只关心字母（忽略大小写），空格、标点、引号都不计入。
解决方案：预处理 + 通用判断
先清洗字符串：只保留字母并转小写，再用前面任一算法判断。
String preprocess(String source) {
return source.replaceAll("[^a-zA-Z]", "").toLowerCase();
}
boolean isLetterBasedAnagramMultiset(String string1, String string2) {
return isAnagramMultiset(preprocess(string1), preprocess(string2));
}
扩展性
- ✅ 若想包含数字：
[^a-zA-Z0-9] - ✅ 若区分大小写：去掉
.toLowerCase() - ✅ 可复用已有判断逻辑，结构清晰
👉 这是处理“语言学意义上变位词”的标准做法，建议封装成工具方法。
7. 总结
| 方法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
|---|---|---|---|---|
| 排序法 | O(n log n) | O(n) | 简单直观 | 性能较差 |
| 计数数组 | O(n) | O(1)（固定256） | 快速高效 | 不适合大字符集 |
| Guava Multiset | O(n) | O(k)（k为唯一字符数） | 灵活、易读 | 依赖外部库 |
| 预处理 + 判断 | O(n) | 视实现而定 | 适应业务需求 | 需额外清洗 |
建议
- 🔹 快速原型 or 小数据：用排序法，简单不踩坑
- 🔹 高性能要求、ASCII 文本：计数数组，极致优化
- 🔹 项目已用 Guava：
Multiset，代码清爽 - 🔹 语言学场景：预处理 + 上述任一方案
所有示例代码已上传至 GitHub：https://github.com/example/string-anagram-demo