当前位置：首页 > news >正文

有效的字母异位词 - 题目笔记

news 2026/3/26 17:19:52

📋题目信息

题目名称：有效的字母异位词
难度等级：简单
题目编号：242
相关标签：哈希表、字符串、排序

🎯题目描述
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

示例：

输入：s = "anagram", t = "nagaram" 输出：true 输入：s = "rat", t = "car" 输出：false

💡核心解题思路

方法一：哈希表计数法（推荐）
使用频次数组统计字符出现次数，通过增减操作判断是否相等。

关键点：

固定大小数组统计字符频率
统计s中字符，减去t中字符
检查最终计数是否全为零

方法二：Timsort排序法
如果两个字符串是异位词，排序后的结果一定相同。

关键点：

利用sorted()函数排序
比较排序后的结果
代码简洁但复杂度较高

🔧完整代码实现

方法一：哈希表计数法

class Solution: def isAnagram(self, s: str, t: str) -> bool: if len(s) != len(t): return False array = [0] * 26 # 统计s中字符频率 for i in range(len(s)): array[ord(s[i]) - ord('a')] += 1 # 减去t中字符频率 for j in range(len(t)): array[ord(t[j]) - ord('a')] -= 1 # 检查是否全为零 for k in range(26): if array[k] != 0: return False return True

优化版本（提前终止）

class Solution: def isAnagram(self, s: str, t: str) -> bool: if len(s) != len(t): return False table = [0] * 26 for char in s: table[ord(char) - ord('a')] += 1 for char in t: table[ord(char) - ord('a')] -= 1 if table[ord(char) - ord('a')] < 0: return False return True

方法二：Timsort排序法

class Solution: def isAnagram(self, s: str, t: str) -> bool: if len(s) != len(t): return False return sorted(s) == sorted(t)

方法三：Counter函数法

from collections import Counter class Solution: def isAnagram(self, s: str, t: str) -> bool: return Counter(s) == Counter(t)

📊复杂度分析

方法	时间复杂度	空间复杂度	说明
哈希表计数法	O(n)	O(1)	最优解法
Counter函数法	O(n)	O(k)	k为不同字符数
Timsort排序法	O(n log n)	O(n)	代码简洁

🛠️核心函数详解

1. len() 函数

len(s) # 获取字符串长度

作用：返回对象的长度（字符数）
应用：长度预检查，快速排除不匹配情况
时间复杂度：O(1)

2. ord() 函数

ord('a') # 返回97 ord('b') # 返回98

作用：将字符转换为对应的ASCII码（整数）
应用：字符到数组索引的映射
关键技巧：ord(char) - ord('a')将’a’-'z’映射到0-25
时间复杂度：O(1)

3. sorted() 函数

sorted("anagram") # 返回 ['a', 'a', 'a', 'g', 'm', 'n', 'r']

作用：对可迭代对象进行排序，返回新的排序后的列表
内部实现：Timsort算法
应用：排序后比较字符串是否相等
时间复杂度：平均O(n log n)，最优O(n)

4. Counter 类

from collections import Counter Counter(s) # 返回字符频率字典

作用：统计可迭代对象中元素的出现次数
应用：直接比较两个字符串的字符频率
时间复杂度：O(n)
空间复杂度：O(k)

📝代码执行流程

以 s = “anagram”, t = “nagaram” 为例（哈希表法）：

初始状态：

array = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]

统计s中字符：

'a' → array[0] += 1 → array[0] = 1 'n' → array[13] += 1 → array[13] = 1 'a' → array[0] += 1 → array[0] = 2 'g' → array[6] += 1 → array[6] = 1 'r' → array[17] += 1 → array[17] = 1 'a' → array[0] += 1 → array[0] = 3 'm' → array[12] += 1 → array[12] = 1 # 结果：array = [3,0,0,0,0,0,1,0,0,0,0,0,1,1,0,0,0,1,0,0,0,0,0,0,0,0]

减去t中字符：

'n' → array[13] -= 1 → array[13] = 0 'a' → array[0] -= 1 → array[0] = 2 'g' → array[6] -= 1 → array[6] = 0 'a' → array[0] -= 1 → array[0] = 1 'r' → array[17] -= 1 → array[17] = 0 'a' → array[0] -= 1 → array[0] = 0 'm' → array[12] -= 1 → array[12] = 0 # 最终：array = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]

检查结果：所有元素都为0，返回True

🎯解题关键点

✅核心思路