[LeetCode]Group Anagrams

Question
Given an array of strings, group anagrams together.

For example, given: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”],
Return:

[
[“ate”, “eat”,”tea”],
[“nat”,”tan”],
[“bat”]
]
Note: All inputs will be in lower-case.

本题难度Medium。

【思路】
对单词进行排序得到​​​key​​​，看是否为同一个单词。同时利用一个HashMap变量保存​​<key，list序号>​​。

【复杂度】
时间 O(NKlogK) 空间 O(N)

【注意】
本题的单词都是lower-case。

【代码】

public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        //require
        List<List<String>> ans=new ArrayList<>();
        if(strs==null)
            return ans;
        Map<String,Integer> map=new HashMap<String,Integer>();
        //invariant
        int num=0;
        for(String s:strs){
            String r=sort(s);
            if(map.containsKey(r)){
                int index=map.get(r);
                ans.get(index).add(s);
            }else{
                map.put(r,num);
                ans.add(new ArrayList<String>());
                ans.get(num).add(s);
                num++;
            }
        }
        //ensure
        return ans;
    }
    private String sort(String s){
        char[] chars=s.toCharArray();
        Arrays.sort(chars);
        return new String(chars);
    }
}