LeetCode 242.有效的字母异位词

这道题目比较简单，主要想要分享的就是解题的思路与思考，首先我们来看看这道题目：

也就是说我们需要找到两个字符串是否含有相同的字母以及字母出现的数目，那么最简单也是我们最容易想到的就是将这两个字符串排序，然后将两个字符串进行比较是否相同。因为Python中集成了排序的方法，所以代码也非常简单：

class Solution(object):
    def isAnagram(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        return sorted(s) == sorted(t)

因为排序算法的最小的事件复杂度为 $O(NlogN)$O(NlogN)，所以排序的解法时间复杂度为 $O(NlogN)$O(NlogN)。我们如何减小时间复杂度呢？答案是用map来进行字母的计数操作，如果计数完成之后两个map相同，那么就可以判定这两个字符串是有效的字母异位词，因为map查询的时间复杂度是 $O(1)$O(1)，那么这种算法的时间复杂度为 $O(N)$O(N)，代码如下所示：

class Solution(object):
    def isAnagram(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        dict1 = {}
        dict2 = {}
        for letter in s:
            dict1[letter] = dict1.get(letter,0) + 1
        for letter in t:
            dict2[letter] = dict2.get(letter,0) + 1
        return dict1 == dict2

所以用map的方式可以减小整个算法的时间复杂度，希望以上的描述对各位读者的算法理解有所帮助，谢谢。