leetcode hot100－02 字母异位词分组

题目：字母异位词分组

难度：中等

地址：https://leetcode.cn/classic/problems/group-anagrams/description/

描述：给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

过程：

　　1、首先啥叫异位词：

　　　　　按定义就是两个字符串里的字符去重之后应该完全一样，同时字符的数量也应该一样。说不清楚，直接举例：

　　　　　abc,cab ，都为a、b、c组成，且a、b、c的数量一样，为异位词

　　　　　abbc，bac，都为a、b、c组成，但是b字母的数量不一样，不是异位词

　　2、解题，将异位词分组到一起

　　　　　如果不是分组异位词，是分组一个班的学生。可以按男女分、出生月份分、居住的街道分，总之就是有一个共同的特性。

　　　　　假设，互为异位词有一个通通属性，可以通过fn(x)获取，那就简单了，我就用一个字典直接进行分组

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        temp_dic = {}
        for itemstr in strs:
            key_str = fn(itemstr)
            if key_str in temp_dic:
                temp_dic[key_str].append(itemstr)
            else:
                temp_dic[key_str] = [itemstr]
        return list(temp_dic.values())

　　　　　　那么，互为异位词他们的共同属性是啥呢？前面我们有解释啥为异位词

　　　　　　　　1、他们有相同的字母组成6

　　　　　　　　2、字母的数量相同

　　　　　　所以，这两个字符串排序后肯定是一样的，那么直接用python默认排序就完事儿。 

　　　　　　我也这么试过了，确实可以，但是感觉逼格不够高，既然是解算法题，还是不要这么直给，毕竟一般练算法都是为了面试，普通　　　　　　　　人谁看算法，得让面试官觉着，没那么直球。

　　　　　　除了排序一样，还有啥一样？

　　　　　　都是26个字母，假设有一个26长度的数组，代表a～z，每个位置代表当前字母的数量，那互为异位词的数组是不是也是一样的，我按照这个思路也来了一遍

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        temp_dic = {}
        for itemstr in strs:
            key_list = [0]*26
            for c in itemstr:
                key_list[ord(c)-ord('a')] += 1
            key_str = ','.join(map(str, key_list))
            if key_str in temp_dic:
                temp_dic[key_str].append(itemstr)
            else:
                temp_dic[key_str] = [itemstr]
        return list(temp_dic.values())

　　　　　　里面其实可以优化的，python中，元祖是可以作为key的，直接讲数组作为key，同时可以定义一样默认数组的字典，就不需要else判断了

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        temp_dic = collections.defaultdict(list)
        for itemstr in strs:
            key_list = [0]*26
            for c in itemstr:
                key_list[ord(c)-ord('a')] += 1
            temp_dic[tuple(key_list)].append(itemstr)
            # if key_str in temp_dic:
            #     temp_dic[key_str].append(itemstr)
            # else:
            #     temp_dic[key_str] = [itemstr]
        return list(temp_dic.values())

　　　　　　再给一个go的实现，注意go的数组是可以作为key的，但是切片不行

 1 func groupAnagrams(strs []string) [][]string {
 2 
 3     tempDic := make(map[[26]int][]string)
 4     for _, str := range strs {
 5         keylist := [26]int{}
 6         for _, c := range str {
 7             keylist[c-'a']++
 8         }
 9         tempDic[keylist] = append(tempDic[keylist], str)
10 
11     }
12     reResult := make([][]string, 0)
13     for _, v := range tempDic {
14         reResult = append(reResult, v)
15 
16     }
17     return reResult
18 
19 }