Anagrams

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

Note: All inputs will be in lower-case.

(An anagram is a type of word play, the result of rearranging the letters of a word or phrase to produce a new word or phrase, using all the original letters exactly once.)
Solution1: with hashmap and iterator
排序后的字符串可以作为一个key，也就是某一个class的id，如此只要对每一个字符串排序，然后建立一个hashmap，key是排序后的串，而value是所有属于这个key类的字符串，这样就可以比较简单的进行分类。假设我们有n个字符串，字符串最大长度是k，那么该算法的时间复杂度是O(nklogk)，其中O(klogk)是对每一个字符串排序（如果用线性算法也可以提高）。空间复杂度则是O(nk)，即hashmap的大小。

public class Solution {
    public ArrayList anagrams(String[] strs) {
        ArrayList res = new ArrayList();
        if(strs == null || strs.length == 0)
            return res;
        
        //用sort过的string作为key， anagrams的arraylist作为value
        HashMap> map = new HashMap>();
        for(int i = 0; i < strs.length; i++) {
            char[] arr = strs[i].toCharArray();
            Arrays.sort(arr);
            String str = new String(arr);
            
            if(map.containsKey(str)) {
                map.get(str).add(strs[i]);
            }else {
                ArrayList list = new ArrayList();
                list.add(strs[i]);
                map.put(str, list);
            }
        }
        
        Iterator iter = map.values().iterator();
        while(iter.hasNext()) {
            ArrayList item = (ArrayList)iter.next();
            if(item.size() > 1) {
                res.addAll(item);
            }
        }
        
        return res;
    }
}

Solution2: with hashmap and set

public class Solution {
    public ArrayList anagrams(String[] strs) {
        ArrayList res = new ArrayList();
        if(strs == null || strs.length == 0)
            return res;
        
        //用sort过的string作为key， anagrams的arraylist作为value
        HashMap> map = new HashMap>();
        for(int i = 0; i < strs.length; i++) {
            char[] arr = strs[i].toCharArray();
            Arrays.sort(arr);
            String str = new String(arr);
            
            if(map.containsKey(str)) {
                map.get(str).add(strs[i]);
            }else {
                ArrayList list = new ArrayList();
                list.add(strs[i]);
                map.put(str, list);
            }
        }
        
        Set set = map.keySet();
            
        for(String s : set) {
            ArrayList val = map.get(s);
            if(val.size() > 1) {
                res.addAll(val);
            }
        }
        return res;
    }
}