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

题目来源自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 False
            
        sArray = [0] * 26
        tArray = [0] * 26
        for sChar, tChar in zip(s,t):
            # print(ord(sChar))
            sArray[ord(sChar) - 97] += 1
            tArray[ord(tChar) - 97] += 1

        return sArray == tArray
1
2
3
4
5
6
7
8
9
10
11
12
13
14

（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
        # 二者 ∩ 的结果 肯定是 magazine
        a = Counter(ransomNote) 
        b = Counter(magazine)
        # ransomNote 和 magazine 的交集是否为 最小子集 (这里最小子集为ransomNote)
        return (a & b) == a
1
2
3
4
5
6
7
8

（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())
1
2
3
4
5
6
7
8
9
10
11
12
13

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

题目描述：
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
解题思路：
最笨的办法就是单向放入子串处理对比
但是每一次移动都是右进左出，简化滑动窗口即可

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        target = [0] * 26
        for w in p:
            target[ord(w) - ord('a')] += 1
        
        n = len(p)
        ans = []
        cur = [0] * 26
        for i, w in enumerate(s):
            cur[ord(w) - ord('a')] += 1
            if i >= n:
                cur[ord(s[i-n]) - ord('a')] -= 1
            if 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26