LeetCode50天刷题计划（Day 26— 字母异位词分组（11.30-12.20）

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

梦想被现实打败了

一、题目

字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

示例

示例 1:
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]

示例 2:
输入: strs = [“”]
输出: [[“”]]

示例 3:
输入: strs = [“a”]
输出: [[“a”]]

提示

1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母

二、思路

这题有各种形成哈希表键值的方法，比如用顺序排序的字符串（排序后异位词字符串必相等），用26个元素的数组计数（表示字母是否的数量），但个人认为都不如这个用质数乘积形成键值（嘻）
用质数表示26个字母，把字符串的各个字母相乘，这样可保证有且只有字母异位词的乘积是相等的。
然后写了 最后一个示例没过，也不知道为啥过不了，数据太大了，可能哪里越界了？？
不懂、梦想被现实打败了。。。
所以换了26个元素的数组做key 嘤

三、代码

1.没过

class Solution:
    def groupAnagrams(self, strs: List[str]) -> 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,91,97,101] #5/6是各两个
        hash_={}
        #遍历
        for i in strs: 
            key=1 
            for j in i:#计算每个元素的key
                key*=prime[ord(j)-97]
            if(key in hash_): #如果key在表中
                hash_[key].append(i)
            else: #如果key不在表中
                hash_[key]=[i]
        #返回
        return list(hash_.values()) #转为列表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2，AC（丑）

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        #定制
        hash_={}
        #遍历
        for i in strs: 
            key_list=[0]*26 
            for j in i:#每个元素的key
                key_list[ord(j)-97]+=1
            key=str(key_list)
            if(key in hash_): #如果key在表中
                hash_[key].append(i)
            else: #如果key不在表中
                hash_[key]=[i]
        #返回
        return list(hash_.values()) #转为列表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16