[Array & String] 242. Valid Anagram 有效的字母异位词

[jotoy]

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

示例 1:

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

示例 2:

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

说明:
你可以假设字符串只包含小写字母。
进阶:
如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-anagram
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

本题只需要判断字符串s和t中每个字母出现次数是否相同。
如果两个字符串长度不同，则一定不为字母异位词，因此可以直接排除。对于相同长度的字符串，可以利用哈希表实现字符的比对。初始化长度为26值为0的数组，如果字符串s中出现了字符'a'，则将数组对应的下标+1，如果在字符串t中出现了相同的字符'a'，则将对应的下标－1。最终通过数组中是否全为0判断两个字符串是否是字母异位词

开始的解法：
初始化1个长为26的数组，没有使用字典，时间复杂度高

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        dic = "abcdefghijklmnopqrstuvwxyz"
        if len(s) != len(t):
            return False
        s_num = [0 for i in range(26)]

        for i in range(len(s)):
            for j in range(26):
                if s[i] == dic[j]:
                    s_num[j] += 1
                if t[i] == dic[j]:
                    s_num[j] -= 1
        if s_num == [0 for i in range(26)]:
            return True
        else:
            return False

升级解法：
定义两个空字典，用于记录出现的字符。优势：由于存在一定可能，字符串中不会出现所有的26个字母，因此使用空字典可以降低空间复杂度。

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        dict1 = {}
        dict2 = {}
        for ch in s:
            dict1[ch] = dict1.get(ch, 0) + 1
            # dict2[ch] = 0
        for ch in t:
            dict2[ch] = dict2.get(ch, 0) + 1
        # for ch in t:
        #     if dict1.get(ch,0) == 0:
        #         return False
        #     dict1[ch] = dict1.get(ch) - 1
        #     if dict1[ch]<0:
        #         return False
        if dict1 == dict2:
            return True
        else:
            return False

学到了：

1. 利用哈希表（python中的字典）解决字符串匹配问题，相比直接使用字符串，可以提升效率，降低时间和空间复杂度。
2. python中字典的get()函数：

dict.get(key, default=None)
返回指定键的值，如果值不在字典中返回default值