LeetCode 有效的字母异位词题解

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。排序法的核心思想是将两个字符串排序后比较是否相等。掌握哈希表的使用方法对于解决类似的问题非常重要。