给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例:

输入: ["eat", "tea", "tan", "ate", "nat", "bat"] 输出: [ ["ate","eat","tea"], ["nat","tan"], ["bat"] ]

思路与代码

对每个字符串重排序，维护一个Map即可。 时间复杂度 O(nklog(k)) n是strs数组的长度 klog(k)是每个字符串排序的复杂度

class Solution { public List<List<String>> groupAnagrams(String[] strs) { Map<String, List<String>> map = new HashMap(); for (String str: strs) { char[] arr = str.toCharArray(); Arrays.sort(arr); String key = String.valueOf(arr); if (!map.containsKey(key)) map.put(key, new ArrayList()); map.get(key).add(str); } return new ArrayList(map.values()); } }

用各字母的数量作为map的key 时间复杂度 O(nk)

class Solution { public List<List<String>> groupAnagrams(String[] strs) { Map<String, List<String>> map = new HashMap(); int[] count = new int[26]; for (String str : strs){ Arrays.fill(count, 0); for (int i = 0; i < str.length(); i++) count[str.charAt(i) -'a']++; StringBuilder sb = new StringBuilder(); for (int i = 0; i < 26; i++){ sb.append('#'); sb.append(count[i]); } String key = new String(sb); if (!map.containsKey(key)) map.put(key, new ArrayList()); map.get(key).add(str); } return new ArrayList(map.values()); } }