数据结构：检查两个字符串是否是字母异位词（anagram）

目录

第一步：思考原始方法

第二步：我们尝试“构造结构”来记录字母出现次数

第三步：用“配料表”比较两个字符串

第四步：代码实现

问题定义

给定两个字符串，例如：

str1 = \"listen\"str2 = \"silent\"

我们想判断：它们是否是字母异位词（anagram）？

我们把这个概念分解：

• 两个字符串的长度必须一样

• 字符的种类和数量必须一一对应：

  A 有 1 个 \'l\'，B 也必须有 1 个 \'l\'
  A 有 1 个 \'s\'，B 也必须有 1 个 \'s\'

第一步：思考原始方法

最原始的直觉做法：

• 对两个字符串分别排序，再逐字符比较

这个方法可行，但它依赖排序：

sort(str1);sort(str2);return str1 == str2;

但我们现在不允许直接使用这种技巧，我们要从头思考：有没有不用排序就能比较两个字符串的本质？

❓真正的本质是什么？

我们深入想一下 anagram 的定义：

• 两个字符串的长度必须相同

• 每个字母的“出现次数”必须完全一样

⚠️ 注意：不是是否包含某些字符，而是包含了几次也要一样！

这是一个典型的“配料清单”问题：

如果 A 和 B 是同一种面包的配方，虽然制作顺序不同，但他们用的材料和数量一模一样，就算作是“同一种面包”。

所以我们的问题转换成：

如何比较两个“配料表”是否完全一致？

第二步：我们尝试“构造结构”来记录字母出现次数

这就回到了我们之前在“查找重复字符”时构造的想法：

我们可以为每个字母设置一个计数器，记录它出现的次数。

参考：数据结构：找出字符串中重复的字符（Finding Duplicates in a String）——使用哈希表 -CSDN博客

我们必须为每一个可能的字符，记录：它出现了几次

但是问题来了：

英文中有26个小写字母，我们不可能为每一个字符手写一个变量。

这显然不现实，我们会意识到：

❗我需要一个“容器”来批量记录 a~z 每个字母的“数量”信息。

我们于是想到：“我们需要一个能按字符索引、可存数量的结构”

如果我们能做出这样的结构：

• \'a\' → 第 0 格子

• \'b\' → 第 1 格子

• ...

• \'z\' → 第 25 格子

那我们就能：

• 对于字符串 A，往里面加材料

• 对于字符串 B，从里面减材料

最后检查这个配料表是否“归零”，即可知道是否完全配平。

第三步：用“配料表”比较两个字符串

设想一个盒子（配料表）H，里面有 26 个格子，初始都是 0。

我们进行以下操作：

阶段 1：处理字符串 A

• 每看到一个字符，就往对应的格子里“加 1”

• 看到 \'l\' → H[11]++

• 看到 \'i\' → H[8]++

• 最后 H 会记录下所有原料的数量

例如：

A = \"listen\"处理后：H[\'l\'-\'a\'] = 1H[\'i\'-\'a\'] = 1H[\'s\'-\'a\'] = 1H[\'t\'-\'a\'] = 1H[\'e\'-\'a\'] = 1H[\'n\'-\'a\'] = 1

阶段 2：处理字符串 B

• 每看到一个字符，就在对应格子“减 1”

B = \"silent\"

每遇到 \'s\' → H[18]--；

每遇到 \'i\' → H[8]--；

如果两个字符串完美配对，最后：

• 每个格子都变成 0！

关键点来了：

如果我们某次减法后，某个格子变成了 负数，说明：

• 字符 B 某个字母出现得比 A 多

• 那肯定不可能是 anagram！

所以我们可以在处理 B 的过程中提前终止判断：

“只要我看到有一个位置减到负数，那就不是了！”

🔍 基本思想

1. 准备一个计数器数组 H[26]，用于记录每个字母的出现情况

2. 遍历字符串 A：

   • 每出现一个字符，就把对应 H 中的计数加 1

3. 遍历字符串 B：

   • 每出现一个字符，就在 H 中减去 1

   • 如果某个字母的计数变成负数，说明 B 中该字符比 A 多 → 肯定不是 anagram

4. 如果全部字符都匹配，最终 H 中每个位置都应为 0

第四步：代码实现

数据结构设计：

我们需要一个「配料表」：

int H[26] = { 0 };

解释：

• H[i] 记录字母 \'a\' + i 的数量差

• 先加 A 的字符 → H[...] += 1

• 再减 B 的字符 → H[...] -= 1

🔹 步骤 1：准备字符串和变量

char A[] = \"listen\";char B[] = \"silent\";int H[26] = { 0 }; // 初始化26个位置为0int i;

 🔹 步骤 2：遍历第一个字符串 A，进行“加法”

for (i = 0; A[i] != \'\\0\'; i++) { H[A[i] - \'a\'] += 1;}

解释：

• 每读取一个字符 ch，将 H[ch - \'a\'] 对应的格子加 1

• \'a\' - \'a\' = 0，\'b\' - \'a\' = 1，...，\'z\' - \'a\' = 25

• 这样刚好把字符映射到 0~25 的范围

🔹 步骤 3：遍历第二个字符串 B，进行“减法”

for (i = 0; B[i] != \'\\0\'; i++) { H[B[i] - \'a\'] -= 1; if (H[B[i] - \'a\'] < 0) { printf(\"Not anagram\\n\"); break; }}

解释：

• 每遇到一个字符就“扣除”一次对应配料

• 一旦发现有某种配料少了（变成负数），立即判定失败！

🔹 步骤 4：如果 B 成功走完（说明没有字符过多）

if (B[i] == \'\\0\') { printf(\"Is anagram\\n\");}

为什么这样判断？

• 如果前面的 for 循环没有被 break 中断，那 B[i] 走到了 \'\\0\'

• 说明整个 B 字符串配对成功，没有任何字符超出配料表

完整代码

#include int main() { char A[] = \"listen\"; char B[] = \"silent\"; int H[26] = { 0 }; int i; // 阶段 1：处理 A，构造配料表 for (i = 0; A[i] != \'\\0\'; i++) { H[A[i] - \'a\'] += 1; } // 阶段 2：处理 B，逐一扣除配料 for (i = 0; B[i] != \'\\0\'; i++) { H[B[i] - \'a\'] -= 1; // 提前终止：某个字母用多了 if (H[B[i] - \'a\'] < 0) { printf(\"Not anagram\\n\"); break; } } // 阶段 3：如果没有被 break 打断，说明是 anagram if (B[i] == \'\\0\') { printf(\"Is anagram\\n\"); } return 0;}