Given an array of strings, group anagrams together.
Example:
Input: ["eat", "tea", "tan", "ate", "nat", "bat"], Output: [ ["ate","eat","tea"], ["nat","tan"], ["bat"] ]
题意：
给定一堆单词，把变位词放一块儿去。
碎碎念：
开始想说“eat” 转charArray {'e', 'a', 't'}
“tea” 转charArray {'t', 'e', 'a'}
这样，我就错误的蜜汁以为以上charArray是相等的！
于是用一个Map<char[], List<Integer>> map 来边扫input 边更新map。
为何要用List<Integer> ? 我蜜汁绕弯的想将index存下，最后再取出index对应的input string。 （自己都翻白眼啊！）
正确且高效的改进是，
sort “eat” 转charArray {'e', 'a', 't'} 为字典排序 {'a', 'e', 't'}
sort “tea” 转charArray {'t', 'e', 'a'} 为字典排序 {'a', 'e', 't'}
Map<String, List<String>> map 来存 <变位词sort后的同一结果， 各种可能的变位词>
Solution1: HashMap
(1) convert each string to charArray, sort such charArray to make sure anagrams has uniform reference
(2) hashmap
(3) get all map.values()
code
/* Time: O(n). We traverse the input array Space: O(n). We allocate a hashmap */ class Solution { public List<List<String>> groupAnagrams(String[] strs) { List<List<String>> result = new ArrayList<>(); // corner case if(strs ==null) return result; Map<String,List<String>> map = new HashMap<>(); for(int i = 0; i< strs.length; i++){ char [] curr = strs[i].toCharArray(); Arrays.sort(curr); // to make sure anagrams has uniform reference String key = String.valueOf(curr); if(!map.containsKey(key)){ map.put(key,new ArrayList<String> ()); } map.get(key).add(strs[i]); } for(List<String> list : map.values()){ // 可以直接简写成 result.add(new ArrayList<>(list)); // || } // \/ return result; // return new ArrayList<>(map.values); } }
转载于:https://www.cnblogs.com/liuliu5151/p/10708256.html
