一定要早日上岸鸭 · July 18, 2021 0

面试题 10.02. 变位词组

编写一种方法,对字符串数组进行排序,将所有变位词组合在一起。变位词是指字母相同,但排列不同的字符串。

首先是法1:哈希+排序

class Solution { public List<List<String>> groupAnagrams(String[] strs) { List<String> list = new ArrayList<String>(); List<List<String>> ret = new ArrayList<>(); Map <String, List> hm = new HashMap<String, List>(); for(String s:strs){ char[] sarr = s.toCharArray(); Arrays.sort(sarr); String key = String.valueOf(sarr); list = hm.getOrDefault(key, new ArrayList<String>()); list.add(s); hm.put(key, list); } for(String key:hm.keySet()) ret.add(hm.get(key)); return ret; } }

法2:模拟 + 计数

由于限定了26个小写字母,所以可以用数组来模拟单词注意cnts[c-'a']是转换为ascii的办法

class Solution { public List<List<String>> groupAnagrams(String[] ss) { List<List<String>> ans = new ArrayList<>(); Map<String, List<String>> map = new HashMap<>(); for (String s : ss) { int[] cnts = new int[26]; for (char c : s.toCharArray()) cnts[c - 'a']++; StringBuilder sb = new StringBuilder(); for (int i : cnts){ sb.append(i); } String key = sb.toString(); System.out.println(key); List<String> list = map.getOrDefault(key, new ArrayList<>()); list.add(s); map.put(key, list); } for (String key : map.keySet()) ans.add(map.get(key)); return ans; } }