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:
For the return value, each inner list’s elements must follow the lexicographic order.
All inputs will be in lower-case.

Thinking:

This question took me a lot of time. First, I want to get a String from the list, and check its anagrams with the rest of the list. And write the algorithm about the anagrams check. But time exceed. Then I try to change my thinking mode of this problem. We should consider the whole String as a element, and if two strings are anagrams, their new string with sorting are the same. So if we use a hashmap to store its previous string and sorted string, the problem will be easy to solve. So we build a hashmap, its key is the string element from the list, and its value is a new list which contains its key’s anagrams. Finally, we get the results from the hashmap and sort them by Collections.sort method.

Solution:

public List<List<String>> groupAnagrams(String[] strs) {
    int count = strs.length;
    List<List<String>> res = new ArrayList<List<String>>();
    if (count == 0)
        return res;
    HashMap<String, List<String>> hash = new HashMap<String, List<String>>();

    for (String str: strs){
        char[] ca = str.toCharArray();
        Arrays.sort(ca);
        String temp = new String(ca);
        if (hash.containsKey(temp)){
            hash.get(temp).add(str);
        }else{
            List<String> tempres = new ArrayList<String>();
            tempres.add(str);
            hash.put(temp, tempres);
        }
    }

    for (List<String> l: hash.values()){
        Collections.sort(l);
        res.add(l);
    }

    return res;
}

Reference:https://en.wikipedia.org/wiki/Anagram
http://javaconceptoftheday.com/anagram-program-in-java/
http://www.cnblogs.com/springfor/p/3874667.html