一道超简单的Leetcode242：异位词，耗时1小时，能学到什么？

小码匠

发布于 2022-06-16 17:14:42

2330

发布于 2022-06-16 17:14:42

文章被收录于专栏：小码匠和老码农

投其所好陪小孩学习

小码匠每天回来最开心的事就是刷道题，小孩不太喜欢看理论性很强的东西，太枯燥了。

我买了一本《算法设计》，本来想让小码匠看，拿到书，我翻了几页，就果断放弃了。

还是自己抽时间看，然后把比较枯燥的知识点想办法转化成比较有意思的知识，这样小码匠更容易接受。

回到正题，今天小码匠刚到家。

开始安排功课

老码农：今天作业多吗？

小码匠：有一点，20分钟能完成。

老码农：那咱们老五样

待完成事
1. 完成作业
2. 刷一道算法题
3. 学习数据可视化
4. 运动30分钟
5. 读《倚天屠龙记》

（基本每天都在重复这几件事，每天都很开心）

如何？

小码匠：OK，那我去写了啊

20分钟后，小码匠顺利写完作业。双减之后，的确爽了不少，可以有更多的时间一起学编程，和小孩沟通。

小码匠：我休息10分钟，吃个苹果就过来哈。

老码农：嗯，去吧。

开始

老码农：今天的题目也不难，但咱们不要为了做题而做题，争取做一道题，搞明白一道。

小码匠：好嘞，你先说题目吧。

老码农：题目是这样的。

题目：有效的字母异位词

地址：https://leetcode-cn.com/problems/valid-anagram/

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

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

示例 1:

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

示例 2:

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

提示:

1 <= s.length, t.length <= 5 * 104
s 和 t 仅包含小写字母

老码农：题目能看懂吗？

小码匠：我语文又不差，当然看的懂

老码农：那你先自己编，我去看会书，编写完了叫我。

小码匠：OK

小码匠的习惯就是不会直接写代码，先思考，然后大致想明白了，再动手编代码。

一会，听到小码匠一阵噼里啪啦声，呼叫老码农。

小码匠：我编好了，是挺简单的。

def isAnagram(s: str, t: str) -> bool:
    new_t = list(t)
    new_s = list(s)
    new_t.sort()
    new_s.sort()
    if new_s == new_t:
        return True
    else:
        return False

老码农：看代码估计没什么问题，你测试了吗？

小码匠：测试不通过敢叫你过来看啊，要不然啊，你又该啰嗦我缺乏工匠精神了。

老码农：那你跑下，我看看结果。

if __name__ == "__main__":
    print(isAnagram("anagram", "nagaram"))
    print(isAnagram("rat", "car"))
    print(isAnagram("rate", "tear"))
    print(isAnagram("ratre", "tear"))

小码匠轻点【Run】按钮，结果如下。

/Users/cynthia/opt/miniconda3/envs/coder/bin/python 
/coder-algorithm/algorithm/strings/anagram.py
True
False
True
False

Process finished with exit code 0

老码农：运行正确。你有没有考虑过其他解决方案啊。

第一次提交

小码匠：我是没想到特别好的方式，反正我就是先排序，然后比较值是不是一样。

小码匠：咱们先提交呗。

老码农：真的现在就提交吗？

小码匠：那当然。

leetcode242-01

leetcode242-02

老码农：数据有点尴尬啊

内存消耗：超过13%选手
用时消耗：超过9%选手

小码匠：这……这不科学啊，难道还能有什么更好的解决办法吗？

老码农：你先分析一下代码吧，

创建了2个新列表对象
又做了2次sort处理

内存消耗和用时消耗肯定有点高啊。

小码匠：唔……那我再想想吧。

第二个方案：更悲剧

小码匠：我用sorted试试，代码很简洁，不知道效率如何。

小码匠噼里啪啦，先删又敲了一行代码。

def isAnagram2(s: str, t: str) -> bool:
    return sorted(s) == sorted(t)

小码匠：我提交吧。

老码农：你，你，提交吧。

leetcode242-03

leetcode242-04

老码农：看你猴急的，这回也挺惨的

消耗内存：超过19%选手
用时：超过63%的选手

总算比上次好些，但有限啊

小码匠：这个，这个，我的代码够简洁的了，性能还这么差。

老码农：知道为啥吗？还记得我给你留过一道题吗？

list.sort和sorted的区别吗？

小码匠：是有点印象，咋啦？

老码农：你真是气人，我给你安排的作业都不好好做，现在去查然后告诉我结果

小码匠：哎，好吧。

小码匠打开谷歌浏览器，打开了菜鸟教程。

小码匠：

list.sort()不创建新对象，直接在原来对象上排序。
sorted是创建一个新对象，排序结果放到新对象中。

哎，又是创建新对像，怪不得耗时这块还是那么糟糕呢。

老码农：继续再想想，相信你能解决的。

小码匠托起小腮帮，开始了思考。

第三个方案

小码匠：老码农，我实在想不出来更好的方案了，我的方案也都是需要循环，估计性能也不好。

老码农：还思考不，放弃了，我们就看看官方解答。

小码匠：放弃吧，看看官方吧。

官方地址：https://leetcode-cn.com/problems/valid-anagram/solution/you-xiao-de-zi-mu-yi-wei-ci-by-leetcode-solution/

老码农：我们来分析下官方的解答吧。

小码匠：嗯，好

方法一：跟我的是一样的，只是他是用Java实现的，
方法二：哈希表，我看看代码。

看了一分钟，小码匠大呼一声，我明白了。

他是先创建一个Hash表
然后循环第一个串计算每个字符的出现次数
然后循环第二个串，减去每个字符串出现次数，如果有小于0的，就说明第二个字符串中出现的字符在第一个中没有。

小码匠：咋没有Python的实现方式啊？

leetcode242-05

老码农：等你来写的呢呗，你用Python写下吧。

小码匠：好的吧。

小码匠有些不情愿，还是噼里啪啦敲起了键盘。

def isAnagram3(s: str, t: str) -> bool:
    x = [0] * 26
    s = s.lower()
    t = t.lower()
    for i in s:
        x[ord(i) - ord('a')] = x[ord(i) - ord('a')] + 1
    for j in t:
        if (x[ord(j) - ord('a')] - 1) < 0:
            return False
        x[ord(j) - ord('a')] = x[ord(j) - ord('a')] - 1
    return x.count(0) == 26

老码农：我们再Run一次，这次估计不仅成绩能提高，而且时间复杂度和空间复杂度都小了。

小码匠：好，走起，提交。

老码农：这回不错

用时：超过62%选手
内存：超过72%选手

小码匠：官方的解答成绩也不太理想啊，才超过这么多选手。这个时间和空间复杂度都有降低的啊。

老码农：应该还有更好的解决方案，真相是需要你不断追寻才能一步一步逼进的。

小码匠：可我真的想不出来更好的解决方案了。

老码农：我记得有个库也是统计次数的。我想想啊。

第四个方案

老码农：我想起来了，你查查Counter这个库，是Python里面的一个计数器类。

小码匠：我不想弄了，都过去一个小时了，我歇会好不啊。

老码农：在调研下吧，以你的小脑袋瓜，很快就解决了，搞到半道就跑了，不是你的风格啊。

小码匠：嗯，我去查查官方资料吧。

“地址：https://docs.python.org/3.8/library/collections.html ”

leetcode242-06

老码农：真棒，加油！

小码匠又是一阵噼里啪啦，代码呈现如下。

def isAnagram(s: str, t: str) -> bool:
    from collections import Counter
    s_count = Counter(s)
    t_count = Counter(t)
    return s_count == t_count

小码匠轻点【Run】，本地测试通过。开始又一次提交，