Python 判断两个字符串是否为字母异位词（anagram）（建议收藏）

💡一则或许对你有用的小广告

欢迎加入小哈的星球 ，你将获得：专属的项目实战 / 1v1 提问 / Java 学习路线 / 学习打卡 / 每月赠书 / 社群讨论

• 新项目:《从零手撸：仿小红书（微服务架构）》 正在持续爆肝中，基于 Spring Cloud Alibaba + Spring Boot 3.x + JDK 17...，点击查看项目介绍 ;演示链接： http://116.62.199.48:7070 ;
• 《从零手撸：前后端分离博客项目（全栈开发）》 2 期已完结，演示链接： http://116.62.199.48/ ;

截止目前， 星球 内专栏累计输出 90w+ 字，讲解图 3441+ 张，还在持续爆肝中.. 后续还会上新更多项目，目标是将 Java 领域典型的项目都整一波，如秒杀系统, 在线商城, IM 即时通讯，权限管理，Spring Cloud Alibaba 微服务等等，已有 3100+ 小伙伴加入学习 ，欢迎点击围观

前言

在编程与算法学习中，判断两个字符串是否为字母异位词（anagram）是一个经典问题。字母异位词指的是由相同的字母重新排列组合而成的两个字符串，例如 "listen" 和 "silent"。这个问题看似简单，但其背后涉及字符串处理、算法效率以及数据结构的灵活运用。本文将从基础概念出发，逐步深入讲解多种实现方法，并结合代码示例和性能分析，帮助读者掌握这一问题的解决思路。

什么是字母异位词（Anagram）？

字母异位词（Anagram）是指两个字符串可以通过重新排列字符顺序，彼此完全匹配的字符串。例如：

• "debit card" 和 "bad credit"
• "evil" 和 "vile"
• "restful" 和 "fluster"

关键点在于：

1. 两个字符串的字符种类和数量必须完全一致。
2. 字符的顺序可以完全不同。

这一特性使得字母异位词的判断问题，本质上是一个字符统计问题。

方法一：排序法（Sorting Method）

基本思路

排序法的核心思想是：

如果两个字符串是字母异位词，那么它们排序后的结果应该完全相同。

例如，"listen" 排序后为 "eilnst"，而 "silent" 排序后同样为 "eilnst"。因此，只需比较排序后的字符串是否相等即可。

实现步骤

1. 预处理输入：确保字符串仅包含字母，并忽略大小写（例如将所有字符转为小写）。
2. 排序字符串：将两个字符串分别排序。
3. 比较排序结果：若排序后的字符串完全相同，则是字母异位词。

代码示例

def is_anagram_sort(s1: str, s2: str) -> bool:
    # 预处理：转为小写并去除非字母字符（假设输入仅含字母）
    s1 = s1.lower()
    s2 = s2.lower()
    
    # 排序并比较
    return sorted(s1) == sorted(s2)

代码解释

• sorted() 函数将字符串转换为排序后的列表。
• 时间复杂度：排序的时间复杂度为 O(n log n)，其中 n 是字符串长度。
• 空间复杂度：排序需要额外的存储空间，为 O(n)。

方法二：计数法（Counting Method）

基本思路

计数法的核心思想是：

统计每个字符出现的次数，若两个字符串的统计结果完全一致，则为字母异位词。

例如，字符串 "apple" 的字符统计为：

• a:1, p:2, l:1, e:1

实现步骤

1. 预处理输入：与排序法相同，确保字符统一为小写。
2. 统计字符次数：遍历字符串，记录每个字符的出现次数。
3. 比较统计结果：若两个统计结果完全相同，则返回 True。

代码示例

def is_anagram_count(s1: str, s2: str) -> bool:
    # 预处理
    s1 = s1.lower()
    s2 = s2.lower()
    
    # 统计字符次数
    count1 = {}
    count2 = {}
    
    for char in s1:
        count1[char] = count1.get(char, 0) + 1
    for char in s2:
        count2[char] = count2.get(char, 0) + 1
    
    return count1 == count2

代码解释

• dict.get(key, default) 方法用于安全地获取或初始化计数。
• 时间复杂度：遍历字符串需要 O(n) 时间，字典比较需要 O(k)（k 是不同字符的数量）。
• 空间复杂度：字典存储需要 O(k) 空间。

方法三：哈希表优化（Hash Table Optimization）

基本思路

哈希表优化是计数法的改进版本，其核心思想是：

通过统一的哈希表，减少存储空间的使用。

具体步骤：

1. 预处理输入：与前两种方法一致。
2. 统一计数：使用一个哈希表，先增加第一个字符串的字符计数，再减少第二个字符串的计数。
3. 检查最终计数：若所有计数均为 0，则说明字符统计一致。

代码示例

def is_anagram_hash(s1: str, s2: str) -> bool:
    s1 = s1.lower()
    s2 = s2.lower()
    
    # 创建计数字典
    count = {}
    
    # 遍历第一个字符串，增加计数
    for char in s1:
        count[char] = count.get(char, 0) + 1
    
    # 遍历第二个字符串，减少计数
    for char in s2:
        if char not in count:
            return False  # s2 中存在 s1 没有的字符
        count[char] -= 1
    
    # 检查所有计数是否为0
    for v in count.values():
        if v != 0:
            return False
    return True

代码解释

• 通过统一的哈希表，空间复杂度降低为 O(k)，但实际可能更优，因为只需要遍历一次第一个字符串和一次第二个字符串。
• 时间复杂度仍为 O(n)，但常数因子较小。

性能对比与选择建议

以下是三种方法的性能对比表格：

选择建议

1. 排序法：简单易实现，适合字符串长度较短（如 ≤ 100 字符）的场景。
2. 计数法或哈希表优化：在长字符串或需要高效处理时更优。
3. 扩展性：若需处理非字母字符（如数字或符号），需在预处理阶段增加过滤逻辑。

进阶优化：位运算与ASCII编码

对于仅包含小写字母的字符串，可以利用位掩码（Bitmask）或 ASCII 码的特性进行优化。例如：

def is_anagram_bitmask(s1: str, s2: str) -> bool:
    # 仅处理小写字母，假设输入已转换为小写
    mask = 0
    for c in s1:
        shift = ord(c) - ord('a')
        mask ^= 1 << shift
    for c in s2:
        shift = ord(c) - ord('a')
        mask ^= 1 << shift
    return mask == 0

位掩码原理

• 每个字符对应一个二进制位。
• 异或（^）操作使得成对出现的字符位被抵消。
• 缺点：仅适用于小写字母且无法检测字符数量超过 1 次的情况。

实际案例与代码调试

案例 1：经典字母异位词

输入：

print(is_anagram_sort("listen", "silent"))  # True
print(is_anagram_count("listen", "silent"))  # True
print(is_anagram_hash("listen", "silent"))  # True

案例 2：大小写与空格处理

print(is_anagram_sort("Debit Card", "Bad Credit"))  # True（预处理后为 "debitcard" 和 "badcredit"）

调试技巧

1. 打印中间结果：输出排序后的字符串或计数字典，验证逻辑是否正确。
2. 边界测试：测试空字符串（""）、单字符（如 "a" vs "a"）、不同长度（如 "a" vs "aa"）。

常见问题与解决方案

Q1：如何忽略大小写和空格？

def preprocess(s: str) -> str:
    return s.lower().replace(" ", "")

Q2：如何处理非字母字符？

def preprocess(s: str) -> str:
    return ''.join([c for c in s.lower() if c.isalpha()])

Q3：时间复杂度是否可以进一步优化？

• 理论上，字母异位词的判断无法突破 O(n) 时间复杂度（需遍历所有字符）。
• 空间优化可通过位掩码或固定大小的数组（如 count[26]）实现。

结论

判断两个字符串是否为字母异位词是一个典型的算法问题，其核心在于字符统计的实现方式。本文介绍了三种方法：排序法、计数法和哈希表优化，并通过性能对比帮助读者选择最优方案。在实际应用中，需结合数据特点（如字符种类、字符串长度）选择合适的方法，并注意预处理步骤（如大小写统一、非字母字符过滤）。通过本文的讲解，读者可以掌握这一问题的完整解决流程，并将其应用于更复杂的场景中。

希望这篇文章能帮助你理解 Python 中字母异位词的判断方法！如果有任何疑问或优化建议，欢迎在评论区交流。