第26章 字符串的排列：判断两个字符串是否为排列（字符计数法）

各位同学，今天我们来聊一个看似简单、实则暗藏玄机的问题——判断两个字符串是否互为排列。

什么叫「互为排列」？说白了就是：两个字符串里出现的字符种类和数量完全一样，只是顺序不同。比如 "abc" 和 "cba"，再比如 "listen" 和 "silent"。嗯，这个场景在实际开发中其实挺常见的——我记得有一次做文本相似度分析，就需要判断两段文本的字符组成是否一致。

那怎么判断呢？最直接的想法：排序后比较。但排序的时间复杂度是 O(n log n)，有没有更快的办法？当然有——字符计数法，也就是用哈希表或数组统计每个字符出现的次数，然后对比。今天我就带你把这个方法吃透。

核心思路：用计数代替排序

字符计数法的核心思想其实很简单：

1. 如果两个字符串长度不同，直接返回 false。
2. 用一个数组（或哈希表）统计第一个字符串中每个字符出现的次数。
3. 遍历第二个字符串，每遇到一个字符，就把对应的计数减 1。
4. 如果某个字符的计数变成负数，说明第二个字符串中该字符多了，返回 false。
5. 遍历完所有字符后，如果所有计数都为 0，说明是排列。

你想想看，这个过程只需要 O(n) 的时间，而且空间复杂度是 O(1)——因为字符集是有限的（比如 ASCII 码只有 128 个字符）。

代码实现：从基础到优化

我们先看一个最基础的版本。假设字符串只包含 ASCII 字符（0-127）。

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool isPermutation(const char* s1, const char* s2) {
    if (s1 == NULL || s2 == NULL) return false;
    
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    if (len1 != len2) return false;
    
    int count[128] = {0};  // ASCII 字符集
    
    // 统计第一个字符串
    for (int i = 0; i < len1; i++) {
        count[(unsigned char)s1[i]]++;
    }
    
    // 减去第二个字符串
    for (int i = 0; i < len2; i++) {
        int idx = (unsigned char)s2[i];
        count[idx]--;
        if (count[idx] < 0) {
            return false;  // 字符多了
        }
    }
    
    return true;
}

这段代码看起来没问题吧？但我告诉你，这里有个坑——字符索引的转换。你看我用了 (unsigned char) 强制转换，为什么？因为 char 在有些编译器上默认是 signed 的，如果字符的 ASCII 码大于 127，直接作为数组下标会变成负数，导致越界访问。我曾经在这个问题上吃过亏，调试了半天才发现是符号扩展的问题。

扩展：支持 Unicode 字符

如果字符串包含 Unicode 字符（比如中文、日文），那 128 大小的数组就不够用了。这时候可以用哈希表。

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

// 简单的哈希表实现（这里用数组模拟，实际可用更复杂的结构）
#define HASH_SIZE 256

typedef struct {
    int key;
    int value;
} HashEntry;

bool isPermutationUnicode(const char* s1, const char* s2) {
    if (s1 == NULL || s2 == NULL) return false;
    
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    if (len1 != len2) return false;
    
    // 这里用数组模拟哈希表，实际项目中建议用标准库的哈希表
    int count[HASH_SIZE] = {0};
    
    for (int i = 0; i < len1; i++) {
        count[(unsigned char)s1[i]]++;
    }
    
    for (int i = 0; i < len2; i++) {
        int idx = (unsigned char)s2[i];
        count[idx]--;
        if (count[idx] < 0) {
            return false;
        }
    }
    
    return true;
}

嗯，这里我偷了个懒，还是用的数组。但原理是一样的——用哈希表来存储字符到计数的映射。对于真正的 Unicode 字符串，建议用 int 类型的数组，大小设为 65536（覆盖基本多语言平面），或者直接用动态哈希表。

性能对比：计数法 vs 排序法

我整理了一个对比表格，方便你直观地看到两种方法的差异：

方法	时间复杂度	空间复杂度	适用场景
排序法	O(n log n)	O(1)（原地排序）	字符串较短，或需要同时得到排序后的结果
字符计数法	O(n)	O(1)（固定字符集）	字符串较长，或对性能要求高

从表格可以看出，字符计数法在时间上完胜，但空间上其实也不差——因为字符集是固定的，所以空间复杂度实际上是 O(1)。

知识结构图

下面我用一张 SVG 图来展示本章的核心知识结构：

进阶思考：如果字符集非常大怎么办？

你可能会问：如果字符集是 Unicode 全集（超过 100 万个码点），那数组就不现实了。这时候怎么办？

我的建议是：用哈希表。C 语言标准库没有哈希表，但你可以自己实现一个简单的，或者用第三方库。不过在实际项目中，我一般会先评估字符集的范围——如果只是英文字母和数字，128 大小的数组就足够了；如果包含中文，我会用 65536 大小的数组（覆盖基本多语言平面）；只有在极少数情况下才需要动态哈希表。

常见错误与避坑指南

• 忘记处理空指针：函数入口一定要检查 s1 和 s2 是否为 NULL，否则程序会崩溃。
• 忽略大小写：如果要求忽略大小写，记得在计数前统一转换成小写或大写。
• 数组越界：用字符做下标时，一定要用 unsigned char 转换，否则可能访问到负数索引。
• 过早返回：在减数过程中发现负数就返回 false，这个优化是安全的，但要注意逻辑正确性。

我曾经接手过一个项目，里面判断字符串排列的代码用了排序法，而且排序是自己实现的冒泡排序——处理 1000 个字符的字符串都要好几秒。我改成计数法后，瞬间出结果。所以说，选对算法真的很重要。

总结

字符计数法判断字符串排列，说白了就是「数数」——数清楚每个字符出现了几次，然后对比。这个方法简单、高效、容易实现，是面试和实际项目中的首选方案。

记住三个要点：

1. 长度不同直接返回 false。
2. 用数组或哈希表统计字符出现次数。
3. 注意字符索引的转换，避免越界。

好了，这一章的内容就到这里。代码不多，但背后的思想值得好好消化。下次遇到类似的问题，不妨先想想能不能用计数法来解决。

---