[leetcode]Anagrams

Anagrams

Given an array of strings, return all groups of strings that are anagrams.

Note: All inputs will be in lower-case.

编程珠玑中的一道题，书中的解法很巧妙，我就直接搬来用了，时间空间复杂度都是O(n)

算法思路：

将每一个单词初始化，记录每个字符的个数，比如aaabca，初始化为a4b1c1。（也可以用排序做初始化，但是时间复杂度略高）

互为Anagrams的单词的初始化字符串是相同的

public class Solution {
    public List<String> anagrams(String[] strs) {
        Map<String,List<String>> map = new HashMap<String,List<String>>();
        for(String s : strs){
            String init = initial(s);
            if(map.get(init) == null){
                List<String> list = new ArrayList<String>();
                list.add(s);
                map.put(init,list);
            }else{
                map.get(init).add(s);
            }
        }
        List<String> res = new ArrayList<String>();
        for(List<String> list : map.values()){
            if(list.size() > 1){
                res.addAll(list);
            }
        }
        return res;
    }
    private String initial(String s){
        
        int[] hash = new int[26];
        
        for(char c : s.toCharArray()){
            hash[c - 'a']++;
        }
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < 26; i++){
            if(hash[i] > 0){
                sb.append((char)('a' + i ) ).append(hash[i]);
            }
        }
        return sb.toString();
    }
}