LeetCode 49: 字母异位词分组 Group Anagrams
题目:
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
Given an array of strings, group anagrams together.
示例:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]说明：
- 所有输入均为小写字母。
- 不考虑答案输出的顺序。
Note:
- All inputs will be in lowercase.
- The order of your output does not matter.
解题思路:
题目要求是 不管字母怎样排序只要字母相同都归为一类, 只要把所有单词的字母按一定规律排列好, 只要每个单词的字母按规律排好后组成的字符串相同, 则归为一类
排序字母解题:
用哈希映射 {Key : Value} Key 为排好序的字符串, Value 为数组, 存储与 Key 字母相同的单词, 遍历每个单词并排序字母, 查找排序好的字符串是否存在于 Keys, 利用哈希映射可将查找操作时间复杂度降为 O(1)
其解题逻辑为(这里按字母升序排列):
输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
建立哈希映射 map = {}
遍历该字符串数组:
第一个单词: "eat" --> "aet"
"aet" 不存在于 map, 建立映射 {"aet" : [ "eat" ] }
第二个单词: "tea" --> "aet"
"aet" 存在于 map, 加入其 Values {"aet" : [ "eat" , "tea" ] }
第三个单词: "tan" --> "ant"
"ant" 不存在于 map, 建立映射 {"aet" : [ "eat" , "tea" ] ; "ant" : [ "tan" ] }
第四个单词: "ate" --> "aet"
"aet" 存在于 map, 加入其 Values {"aet" : [ "eat" , "tea" , "ate" ] ; "ant" : [ "tan" ] }
......
map = {"aet" : [ "eat" , "tea" , "ate" ] ; "ant" : [ "tan" , "nat"] ; "abt" : [ "bat" ] }
返回该哈希映射的 Values 组成的数组:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]复杂度:
- 时间复杂度：O(N*(K*logK))，其中 N 是 strs 的长度，而 K 是 strs 中字符串的最大长度。遍历每个字符串时复杂度为 O(N)。使用内置排序函数排序字符串中的字母的时间复杂度为 O(K*logK)。
- 空间复杂度：O(N*K)，存储在 map 中数据所占用的空间。
统计字频解题:
这种解题方法还可以再优化, 可以省略对字符串排序的操作。
仔细想想,一个单词最多由 26 个英文字母组成, 不就也可以建立一个哈希映射吗? 如:
对于单词 "aeat" :
建立哈希映射{ 'a' : 2 ; 'e' : 1; t : 1 }key 为出现的单词, value 出现的频次。如果遍历每个 key 判断字母是否相等, 再判断出现次数是否相等, 这显然是更复杂了。
可以将每个字母出现的频次组成连续字符:
每个字母 a-z 出现频次: [2,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0]
组成字符串: "20001000000000000001000000"只需判断每个单词的字母频次字符串是否相同就可以了。
对于求词频还可以优化, 字母数量固定 26 个, 直接建立一个长度为 26 的数组, 其索引代表二十六个字母位, 遍历单词中的字母, 字母每出现一次, 数组中代表该字母的元素值加 1。
这样就避免了排序操作
排序字母解题:
Java:
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
if(strs.length==0) return new ArrayList<>();
Map<String, List<String>> map = new HashMap<>();//建立映射关系
for (String s : strs) {//遍历该字符串数组
char[] chs = s.toCharArray();//转成字符
Arrays.sort(chs);//排序字符串字母
String key = String.valueOf(chs);//转成字符串
if(!map.containsKey(key)) map.put(key, new ArrayList<>());//如果 key 不存在, 新建映射关系
map.get(key).add(s);//加入其对应的 Value 所在的数组
}
return new ArrayList(map.values());//返回 Values 组成的数组
}
}Python:
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
ans = collections.defaultdict(list) # 建立映射关系
for s in strs: # 遍历该字符串数组
ans[tuple(sorted(s))].append(s) # sorted(s):排序字符串字母, 并加入其对应的 Value 所在的数组
return ans.values() # 返回 Values 组成的数组统计字频解题:
Java:
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
if (strs.length == 0) return new ArrayList<>();
Map<String, List<String>> map = new HashMap<>();// 建立映射关系
for (String s : strs) {//遍历该字符串数组
int[] count = new int[26];//建立一个 26 字母的映射关系
for (char c : s.toCharArray()) count[c - 'a']++;//遍历字字符串每个字母统计每个字母出现的频次
String key = Arrays.toString(count);//转成字符串
if (!map.containsKey(key)) map.put(key, new ArrayList<>());//如果 key 不存在, 新建映射关系
map.get(key).add(s);//加入其对应的 Value 所在的数组
}
return new ArrayList(map.values());//返回 Values 组成的数组
}
}Python:
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
ans = collections.defaultdict(list)# 建立映射关系
for s in strs: # 遍历该字符串数组
count = [0] * 26 # 建立一个 26 字母的映射关系
for c in s: # 遍历字字符串每个字母
count[ord(c) - 97] += 1 # 每个字母出现的频次(元素值)加1
ans[tuple(count)].append(s) # 加入其对应的 Value 所在的数组
return ans.values() # 返回 Values 组成的数组欢迎关注微信.公..众号: 爱写Bug
