代码随想录一一一哈希表一一一有效的字母异位词

题目来源自leetcode与代码随想录

（1）242.有效的字母异位词

题目描述：

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

示例 1: 输入: s = “anagram”, t = “nagaram” 输出: true

示例 2: 输入: s = “rat”, t = “car” 输出: false

解题思路：

统计词频即可

class Solution:def isAnagram(self, s: str, t: str) -> bool:# 异常检测if len(s) != len(t):return FalsesArray = [0] * 26tArray = [0] * 26for sChar, tChar in zip(s,t):# print(ord(sChar))sArray[ord(sChar) - 97] += 1tArray[ord(tChar) - 97] += 1return sArray == tArray

（2）383.赎金信

题目描述：

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

解题思路：

既然A从B中来，说明A是B的真子集，那A∩B=A

class Solution:def canConstruct(self, ransomNote: str, magazine: str) -> bool:# ransomNote 从属于 magazine# 二者 ∩ 的结果 肯定是 magazinea = Counter(ransomNote) b = Counter(magazine)# ransomNote 和 magazine 的交集是否为 最小子集 (这里最小子集为ransomNote)return (a & b) == a

（3）49.字母异位词分组

题目描述：

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

解题思路：

确定每类异位的共同之处，同分异构，排序设置键值，归类即可

class Solution:def groupAnagrams(self, strs: List[str]) -> List[List[str]]:res = []dic = {}for s in strs:keys = "".join(sorted(s))if keys not in dic:dic[keys] = [s]else:dic[keys].append(s)return list(dic.values())

（4）438.找到字符串中所有字母异位词

题目描述：

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

解题思路：

最笨的办法就是单向放入子串处理对比

但是每一次移动都是右进左出，简化滑动窗口即可

class Solution:def findAnagrams(self, s: str, p: str) -> List[int]:target = [0] * 26for w in p:target[ord(w) - ord('a')] += 1n = len(p)ans = []cur = [0] * 26for i, w in enumerate(s):cur[ord(w) - ord('a')] += 1if i >= n:cur[ord(s[i-n]) - ord('a')] -= 1if cur == target:ans.append(i-n+1)return ans# 笨蛋解法# target,l = Counter(p), len(p)# res = []# for idx in range(len(s)-l+1):#if Counter(s[idx:idx+l]) == target:# res.append(idx)# return res

如果觉得《代码随想录一一一哈希表一一一有效的字母异位词》对你有帮助，请点赞、收藏，并留下你的观点哦！