Group Anagrams

Question: Given an array of strings, group anagrams together.

Example:

Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note:

• All inputs will be in lowercase.
• The order of your output does not matter.

You may view the full question here.

Approach 1: Let’s try a simple solution for starters. All anagrams when sorted will look the same. This can easily be leveraged as a key in a map for anagram lists. The code would look something like this —

//Approach 1:
//Runtime: 9ms
//Memory usage: 43.2MB
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, List<String>> map = new HashMap();
        List<List<String>> result = new ArrayList();
        for(String s : strs){
            String sortS = sortString(s);
            List<String> list = new ArrayList();
            if(map.containsKey(sortS)){
                list = map.get(sortS);
            }
            list.add(s);
            map.put(sortS, list);
        }
        for(String key : map.keySet()){
            result.add(map.get(key));
        }
        return result;
    }
    
    private String sortString(String s){
        char[] array = s.toCharArray();
        Arrays.sort(array);
        return String.valueOf(array);
    }
}

Find more posts here.

Cheers & Chao!