LeetCode 有效的字母异位词题解
题目描述
给定两个字符串s和t，编写一个函数来判断t是否是s的字母异位词。
示例：
输入：s = "anagram",t = "nagaram"
输出：true
输入：s = "rat",t = "car"
输出：false
解题思路
方法：哈希表
思路：
- 使用哈希表来解决这个问题。
- 首先检查两个字符串的长度是否相等，如果不相等，直接返回 False。
- 创建一个哈希表来统计字符串
s中每个字符出现的次数。 - 遍历字符串
t，对于每个字符，如果在哈希表中不存在或计数为 0，返回 False；否则将哈希表中的计数减 1。 - 如果遍历完成，返回 True。
复杂度分析：
- 时间复杂度：O(n)，其中 n 是字符串的长度。每个字符最多被访问一次。
- 空间复杂度：O(1)，最多需要存储 26 个字母。
代码实现
方法：哈希表
# 有效的字母异位词（哈希表） def is_anagram(s, t): if len(s) != len(t): return False count = {} # 统计字符串 s 中每个字符出现的次数 for char in s: count[char] = count.get(char, 0) + 1 # 遍历字符串 t，检查每个字符 for char in t: if count.get(char, 0) == 0: return False count[char] -= 1 return True # 测试 def test_is_anagram(): print(is_anagram("anagram", "nagaram")) # 输出：True print(is_anagram("rat", "car")) # 输出：False if __name__ == "__main__": test_is_anagram()方法：排序
# 有效的字母异位词（排序） def is_anagram_sort(s, t): return sorted(s) == sorted(t) # 测试 def test_is_anagram_sort(): print(is_anagram_sort("anagram", "nagaram")) # 输出：True print(is_anagram_sort("rat", "car")) # 输出：False if __name__ == "__main__": test_is_anagram_sort()测试用例
测试用例 1：有效字母异位词
输入：s = "anagram",t = "nagaram"
输出：true
测试用例 2：无效字母异位词
输入：s = "rat",t = "car"
输出：false
总结
有效的字母异位词是一个经典的哈希表问题，它可以通过哈希表或排序来解决。
哈希表法的核心思想是：统计字符串s中每个字符出现的次数，然后遍历字符串t，检查每个字符是否在哈希表中存在且计数大于 0。
排序法的核心思想是：将两个字符串排序后比较是否相等。
掌握哈希表的使用方法，对于解决类似的问题非常重要。
