题目描述（中等难度）

给定多个字符串，然后把它们分类。只要字符串所包含的字符完全一样就算作一类，不考虑顺序。

解法一

最通用的一种解法，对于每个字符串，比较它们的每个字符出现的个数是否相等，相等的话就把它们放在一个 list 中去，作为一个类别。最外层写一个 for 循环然后一一比较就可以，还可以用一个等大的布尔型数组来记录当前字符串是否已经加入的了 list 。比较两个字符串的字符出现的次数可以用一个 HashMap，具体看代码吧。

时间复杂度：两层 for 循环，再加上比较字符串，如果字符串最长为 K，总的时间复杂度就是 O（n²K）。

空间复杂度：O（NK），用来存储结果。

解法一算是比较通用的解法，不管字符串里边是大写字母，小写字母，数字，都可以用这个算法解决。这道题的话，题目告诉我们字符串中只有小写字母，针对这个限制，我们可以再用一些针对性强的算法。

下边的算法本质是，我们只要把一类的字符串用某一种方法唯一的映射到同一个位置就可以。

解法二

参考官方给的。

我们将每个字符串按照字母顺序排序，这样的话就可以把 eat，tea，ate 都映射到 aet。其他的类似。

空间复杂度：O（NK），用来存储结果。

解法三

参考，利用算术基本定理。

利用这个，我们把每个字符串都映射到一个正数上。

用一个数组存储质数 prime = {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}。

然后每个字符串的字符减去 ‘ a ‘ ，然后取到 prime 中对应的质数。把它们累乘。

例如 abc ，就对应 ‘a’ - ‘a’， ‘b’ - ‘a’， ‘c’ - ‘a’，即 0, 1, 2，也就是对应素数 2 3 5，然后相乘 2 3 5 = 30，就把 “abc” 映射到了 30。

时间复杂度：O（n * K），K 是字符串的最长长度。

空间复杂度：O（NK），用来存储结果。

解法四

参考这里，记录字符串的每个字符出现的次数从而完成映射。因为有 26 个字母，不好解释，我们假设只有 5 个字母，来看一下怎么完成映射。

首先初始化 key = “0#0#0#0#0#”，数字分别代表 abcde 出现的次数，# 用来分割。

这样的话，”abb” 就映射到了 “1#2#0#0#0”。

“cdc” 就映射到了 “0#0#2#1#0”。

“dcc” 就映射到了 “0#0#2#1#0”。

时间复杂度： O（nK）。

空间复杂度：O（NK），用来存储结果。

总

利用 HashMap 去记录字符的次数之前也有遇到过，很常用。解法三中利用质数相乘，是真的太强了。

添加好友一起进步~

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情