49. Group Anagrams

Posted on | Edited on | In , |

题目

https://leetcode.com/problems/group-anagrams/description/

想法

这个题实际上想法应该就是那样的吧，遍历，然后维护一个个的集合，hash到相应的集合中

用python做了下，主要的时间花在了研究python的语法上

这道题用C/C++还真要花点功夫

自己最先想的是把一个字符串hash到一个独立的数上，就是只要字母相同，顺序不同是一个hash，但是没有找到这样的一个hash函数

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        m = {}
        for str in strs:
            inserted = False
            tmp = ''.join(sorted(str))
            if tmp in m:
                m[tmp].append(str)
                inserted = True
            else:
                m[tmp] = [str]
        return list(m.values())

回顾

高级语言一些封装好的东西，真的是太方便了

看了别人的解答，有这样的一个hash函数而自己没有想到

用素数！
每个字母用一个素数表示
于是，一个str用每个字母的乘积表示，这不会重复！！！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from functools import reduce
class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        prime = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101]
        m = {}
        for s in strs:
            # v = reduce(lambda x, y: prime[ord(x) - 97] * prime[ord(y) - 97], s)
            v = 1
            for c in s:
                v *= prime[ord(c) - 97]
            if v in m:
                m[v].append(s)
            else:
                m[v] = [s]
        return list(m.values())

用py写了下，本以为会beat >90%，没想到不快反慢了，这可能是python的原因吧，或者python本身的dictionary很高效