LeetCode:242 有效的字母异位词(附:哈希表 list & map & set基础)

相关的基础详见下面两个链接:
链接1
链接2
主要包含list map set 的一些基本操作。

题目描述:
给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。
注意:若 s 和 t 中每个字符出现的次数都相同,则称 s 和 t 互为字母异位词
示例:
1)输入: s = “anagram”, t = “nagaram”
输出: true
2)输入: s = “rat”, t = “car”
输出: false
思路1:
把两个单词都进行按照字典顺序排序,比较排序后的两个数组是否相同。

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        a = sorted(s)
        b = sorted(t)
        if a == b:
            return True
        else:
            return False

时间复杂度:O(nlogn)。
思路2:
利用map对两个字符串进行计数,{letter:count},比较两个map是否相同。

class Solution(object):
    def isAnagram(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        s_d = {}
        t_d = {}
        for i in s:
            if i in s_d:
                s_d[i] = s_d[i] + 1
            else:
                s_d[i] = 1
        for j in t:
            if j in t_d:
                t_d[j] = t_d[j] + 1
            else:
                t_d[j] = 1
        if s_d == t_d:
            return True
        else:
            return False

时间复杂度为:O(N)。
本思想代码优化→利用map中的get函数,简化统计部分的代码:

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        dict1, dict2 = {}, {}
        for i in s:
            dict1[i] = dict1.get(i,0) + 1
        for j in t:
            dict2[j] = dict2.get(j,0) + 1
        return dict1 == dict2

思路3:
不用map,而是自己建立一个hash,因为一共有二十六个字母,所以统计每个字母都出现了几次即可,比较两个统计的结果是否相同。

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        dict1, dict2 = [0]*26, [0]*26
        for i in s:
            dict1[ord(i)-ord('a')] += 1
        for j in t:
            dict2[ord(j)-ord('a')] += 1
        return dict1 == dict2
上一篇:攻防世界部分题目+python学习


下一篇:打工人都觉得香的Java程序员306道面试秘笈,爆肝