首页 > itarticle > leetcode49_group_anagrams

leetcode49_group_anagrams

admin 11月 13, 2020 0

把anagrams(颠倒字母顺序产生的单词)放在一起输出

image-20181214211829327

暴力解会超时

思路一：

很自然的想到把字符串排序，然后用hash表来保存

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
class (object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        hash_result = dict()
        result = []
        pos = 0
        for item in strs:
            sitem = self.sort(item)
            if(sitem not in hash_result):
                hash_result[sitem] = pos
                result.append([])
                result[pos].append(item)
                pos+=1
            else:
                result[hash_result[sitem]].append(item)
        return result
                                       
    def sort(self,s):
        return "".join(sorted(list(s)))

思路二：

不同素数的乘积不同，可以用素数来代替26个字母，然后用素数的乘积去代替思路一中字符串的排序

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
27
 
class (object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """       
        hash_result = dict()
        result = []
        pos = 0
        for item in strs:
            mul = self.multi(item)
            if(mul not in hash_result):
                hash_result[mul] = pos
                result.append([])
                result[pos].append(item)
                pos+=1
            else:
                result[hash_result[mul]].append(item)
        return result
     
    
    def multi(self,s):
        primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103]; 
        result = 1
        for i in s:
            result *= primes[(ord(i)-97)]
        return result
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能