题目来源自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
如果觉得《代码随想录一一一哈希表一一一有效的字母异位词》对你有帮助,请点赞、收藏,并留下你的观点哦!