[python 刷题] 242 Valid Anagram

[python 刷题] 242 Valid Anagram

题目：

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

这里 Anagram 的定义就是可以通过重新排序获得的单词，如 cat 可以获得 act，这种，所以满足的条件有两个：

1. 字串 A 里包含的字母和字串 B 一样多
2. 字串 A 中出现字母的频率与字串 B 一样多

我刚开始的写法是这样的：

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        # s being an anagram of t means:
        #   1. same length
        #   2. same # of chars
        if len(s) != len(t):
            return False

        # create a dict to store key val frequency
        char_dict = {}
        for l in s:
            if l in char_dict:
                char_dict[l] = char_dict[l] + 1
            else:
                char_dict[l] = 1

        # find if all chars appeared in the dict
        for l in t:
            if l not in char_dict:
                return False
            if char_dict[l] == 1:
                del char_dict[l]
            else:
                char_dict[l] = char_dict[l] - 1

        return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

第一个检查字符串的长度，二者不一致就可以直接返回 false

然后进入两个循环，第一个循环创建一个 dict，进行字符和频率的 mapping，第二个循环检查当前字符是否出现在 dict 中，如果没有返回 false，如果有，那么出现的频率减少

如果第二个循环走完了，就代表两个字符的出现的字符串频率一致，也就可以返回 true

写完后我参考了一下别人的写法，发现一个更优雅的答案：

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False

        countS, countT = {}, {}

        for i in range(len(s)):
            countS[s[i]] = 1 + countS.get(s[i], 0)
            countT[t[i]] = 1 + countT.get(t[i], 0)
        return countS == countT

1
2
3
4
5
6
7
8
9
10
11
12

我找了一下，dict 中的 get 第二个参数为默认值，即当当前值不存在于 dict 中使用的值，这样可以减少一重 if/else

比较两个 dict 这个我找了下资料， Comparing two dictionaries and checking how many (key, value) pairs are equal

中提到了 python 的文档中 Mapping Types — dict¶ 用了这个案例：

The following examples all return a dictionary equal to {"one": 1, "two": 2, "three": 3}:

>>> a = dict(one=1, two=2, three=3)
>>> b = {'one': 1, 'two': 2, 'three': 3}
>>> c = dict(zip(['one', 'two', 'three'], [1, 2, 3]))
>>> d = dict([('two', 2), ('one', 1), ('three', 3)])
>>> e = dict({'three': 3, 'one': 1, 'two': 2})
>>> a == b == c == d == e
True
1
2
3
4
5
6
7

Providing keyword arguments as in the first example only works for keys that are valid Python identifiers. Otherwise, any valid keys can be used.

另一个 post What does the == operator actually do on a Python dictionary? 中提到，== 中有提到，== 的结果为 true 的情况 sorted(key, value) 结果完全一致，第一条回答找了一个 python 的源码实现，说内部进行递归调用判断 dict 中每个元素都是相通的，不过目前代码的 reference 消失了

总结就是，如果两个 dict 的 key 相同，每个 key 的 value 也相同，就可以用 ==

更新于 2023-09-30

利用其 == 的特点，再使用 collections.Counter，可以一行搞定：

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