哈希题解——有效的字母异位词【LeetCode】

242. 有效的字母异位词

方法一：

算法思路

1. 字母异位词的特点：

   • 两个字符串的字母组成完全相同，只是排列顺序不同。
   • 例如，"anagram" 和 "nagaram" 是字母异位词，因为它们都包含字母 a、n、g、r、m。

2. 核心思想：

   • 使用一个长度为26的数组 record 来记录每个字母的出现次数。
   • 遍历字符串 s，对每个字符的出现次数进行累加。
   • 遍历字符串 t，对每个字符的出现次数进行递减。
   • 如果最终 record 数组中的所有元素都为0，说明 s 和 t 是字母异位词；否则，不是。

3. 具体步骤：

   • 初始化 record 数组为全0。
   • 遍历 s，将每个字符映射到 record 数组的对应位置，并累加计数。
   • 遍历 t，将每个字符映射到 record 数组的对应位置，并递减计数。
   • 检查 record 数组是否全为0，如果是，返回 True；否则，返回 False。

class Solution:def isAnagram(self, s: str, t: str) -> bool:record = [0] * 26for i in range(len(s)):#并不需要记住字符a的ASCII，只要求出一个相对数值就可以了record[ord(s[i]) - ord("a")] += 1print(record)for i in range(len(t)):record[ord(t[i]) - ord("a")] -= 1for i in range(26):if record[i] != 0:#record数组如果有的元素不为零0，说明字符串s和t 一定是谁多了字符或者谁少了字符。return False#如果有一个元素不为零，则可以判断字符串s和t不是字母异位词breakreturn True

时间复杂度分析

1. 遍历字符串 s 和 t：假设 s 和 t 的长度分别为 n 和 m，则遍历的时间复杂度为 O(n + m)。
2. 检查 record 数组：数组长度为26，检查的时间复杂度为 O(1)（常数时间）。
3. 总时间复杂度：O(n + m)。

空间复杂度分析

1. record 数组：数组长度为26，空间复杂度为 O(1)（常数空间）。
2. 总空间复杂度：O(1)。

方法二：

导入defaultdict库来进行编写

from collections import defaultdictclass Solution:def isAnagram(self, s: str, t: str) -> bool:s_dict = defaultdict(int)t_dict = defaultdict(int)for x in s:s_dict[x] += 1for x in t:t_dict[x] += 1return s_dict == t_dict

时间复杂度分析

和上面一个方法一致

空间复杂度分析

和上面一个方法一致