[虚拟机OA]Group Anagram 变位词归类

发布时间：2020-12-15 07:47:25 所属栏目：Java 来源：网络整理

导读：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

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‘,‘t‘}? 为字典排序?{‘a‘,‘t‘}?

sort?“tea” 转charArray {‘t‘,‘a‘}? 为字典排序?{‘a‘,‘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);
    }
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!