写在前面：
不知不觉已经研二下了，既然选择以后走AI这条路，不可避免地也得刷一刷leetcode题目，因为招聘的时候笔试总是要用到的。首先刷一刷leetcode的hot 100题，好记性赶不上烂笔头，记录下来在写这些算法题中的收获给自己看。
参考资料：
考点：哈希 & [题干]
这题没做出来，第一次提交做错了，第二次提交超时了。
1. 两个错误的思路
这题的主体思路其实很明晰，"abc"和"bca"是同义词，应该分为一类放到同一个列表中，那么如何构造这种能蕴含排序不变性质的数据结构？我首先想到的是使用集合即set，写出了如下代码：
class Solution(object): def groupAnagrams(self, strs): """ :type strs: List[str] :rtype: List[List[str]] """ result_dict = {} for onestr in strs: onestr_set = set([s for s in onestr]) FLAG = True for ref_key in result_dict.keys(): ref_key_set = set([s for s in ref_key]) if onestr_set == ref_key_set: result_dict[ref_key].append(onestr) FLAG = False if FLAG: result_dict[onestr] = [onestr] # print(onestr) result = [] for value in result_dict.values(): result.append(value) return result
但是报了错，因为题干中埋了坑，即每个字母并不是只出现一次，这样的话["daaa"]和["aaad"]对应的集合都是("a", "d")，却并不是异位词。
既然用集合不能当做异位同义词的标志符，那么就用字典吧，字典的键是第一次出现的异位词，后面没来一个异位词都对其进行归类append，但是这次却超时了。。只通过了111/118，如下：
class Solution(object): def groupAnagrams(self, strs): """ :type strs: List[str] :rtype: List[List[str]] """ result_dict = {} for onestr in strs: onestr_set = dict() for s in onestr: if s in onestr_set.keys(): onestr_set[s] += 1 else: onestr_set[s] = 1 FLAG = True for ref_key in result_dict.keys(): ref_key_set = dict() for s in ref_key: if s in ref_key_set.keys(): ref_key_set[s] += 1 else: ref_key_set[s] = 1 if onestr_set == ref_key_set: result_dict[ref_key].append(onestr) FLAG = False if FLAG: result_dict[onestr] = [onestr] # print(onestr) result = [] for value in result_dict.values(): result.append(value) return result
2. 正确的思路
实际上，我忽略了一个至关重要的性质，即异位词只要进行字符串排序，则会有唯一确定的键。使用这种性质就可以写出如下正确的代码：
class Solution(object): def groupAnagrams(self, strs): """ :type strs: List[str] :rtype: List[List[str]] """ onestr_set = collections.defaultdict(list) for onestr in strs: onestr_set["".join(sorted(onestr))].append(onestr) # print(onestr) result = [] for value in onestr_set.values(): result.append(value) return(result)
可见正确的题解同样使用了字典来进行异位词的分类（这个显然，因为输出是一个一个的列表），其他的就没什么特别的了
3.小tips
读官方题解的时候对collections.defaultdict这个点有点好奇，collections这个东西我是知道的，里面有一些扩展的数据结构，具体是哪些数据结构我就不知道了。普通的字典在查询的键不存在时会抛出错误，而collections.defaultdict在查询到不存在的键时会创建，默认使用的是这个方法传递的一个method即list，运行时它会调用list()生成一个空的列表，就是这样。