04 Hash Table

242.有效的字母异位词

题目描述

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

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

输入: s = "rat", t = "car"
输出: false

题目链接：https://leetcode-cn.com/problems/valid-anagram/

解法 1：排序后求解

将字符串转换为列表，排序后判断是否相等。时间复杂度为$O(n\log{n})$。（Python 语言排序的时间复杂度为$O(n\log{n})$）

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        s,t = list(s),list(t)
        s.sort()
        t.sort()
        return s == t

解法 2：使用哈希表

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        # 构造hash table
        words = [chr(i) for i in range(97,123)]
        values = [0] * 26
        word_s = dict(zip(words,values))
        # 遍历两个字符串，最后判断字典是否每个值都为空
        for i in range(len(s)):
            word_s[s[i]] += 1
            word_s[t[i]] -= 1
        for i in word_s:
            if word_s[i] != 0:
                return False
        return True

解法 3：使用 collections.Counter 函数

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return collections.Counter(s) == collections.Counter(t) 

解法 4：使用 collections.defaultdict 函数

国际站看到的，也是一种骚操作

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        tracker = collections.defaultdict(int)
        for x in s: tracker[x] += 1
        for x in t: tracker[x] -= 1
        return all(x==0 for x in tracker.values())

49.字母异位词分组

题目描述

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例:

输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

解法 1：哈希表

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        dict = {}
        for item in strs:
            key = tuple(sorted(item))
            dict[key] = dict.get(key, []) + [item]
        return list(dict.values())

注意 dict 的 get()方法，可以不用写非必要的 if else。

1.两数之和

题目描述

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

你可以按任意顺序返回答案。

示例 ：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

哈希表解法

这题可以采用哈希表来解，也是最优的解法。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashtable = dict()
        # i是下标
        # num是对应的值
        for i, num in enumerate(nums):
            if target - num in hashtable:
                return [hashtable[target - num], i]
            hashtable[nums[i]] = i
        return []