Leetcode: Anagrams

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

Note: All inputs will be in lower-case.

Understand the problem:
As described in the problem, given an array of strings, return all groups of strings that are anagrams. Note that all inputs will be lower-case. 

First of all, we must understand what is anagrams? Any word or phrase that exactly reproduces the letters in another order is an anagram. For example, 
abcd, acbd, dcba are anagrams. 

We can take an example to illustrate this question. For the array S = {"abc", "bca", "ab", "acd", "ba"}, the result is ["abc", "bca", "ab", "ba"].

Solution:
To check if two words are anagram, there are usually two methods. The first method is to use a hash map. The first word is added into the map, and delete each character for the second word, if then the hash map becomes zero, the two words are anagrams. In the second method, we sort the two words and compare. If they are the same, they are anagrams. 

Back to this problem where we has a list of words with possible different length. The idea is to use a hash table, where the key store the sorted string, and the value stores the list of anagrams. At last, we copy all the anagrams into the list. 

Code (Java):

public class Solution {
    public List<String> anagrams(String[] strs) {
        List<String> result = new ArrayList<String>();
        if (strs == null || strs.length == 0) {
            return result;
        }
        
        Map<String, ArrayList<String>> hashMap = new HashMap<String, ArrayList<String>>();
        
        for (int i = 0; i < strs.length; i++) {
            char[] word = strs[i].toCharArray();
            
            Arrays.sort(word);
            String key = new String(word);
            
            if (hashMap.containsKey(key)) {
                hashMap.get(key).add(strs[i]);
            } else {
                ArrayList<String> value = new ArrayList<String>();
                value.add(strs[i]);
                hashMap.put(key, value);
            }
        }
        
        // dump the anagrams to the result list
        Set<String> keySet = hashMap.keySet();
        
        for (String key : keySet) {
            List<String> temp = hashMap.get(key);
            if (temp.size() > 1) {
                result.addAll(temp);
            }
        }
        
        return result;
    }
}

Discussion:
Now let's analyze the time complexity. For the string array with length n, each string has the complexity of O(mlogm), where m is the length of each word. So the total time complexity is O(nm logm). The space complexity is O(n).

Summary:
Take away message for this question:
1. Learn the two methods to check two words are anagrams. 
2. Learn how to iterate the hash map and dump the values out. 

Update on 9/29/15:

public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> result = new ArrayList<List<String>>();
        if (strs == null || strs.length == 0) {
            return result;
        }
        
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] arr = str.toCharArray();
            Arrays.sort(arr);
            String sorted = new String(arr);
            if (map.containsKey(sorted)) {
                List<String> anas = map.get(sorted);
                anas.add(str);
            } else {
                List<String> anas = new ArrayList<>();
                anas.add(str);
                map.put(sorted, anas);
            }
        }
        
        // Iterate the hashmap and output the results
        Iterator it = map.entrySet().iterator();
        while (it.hasNext()) {
            Map.Entry pair = (Map.Entry) it.next();
            List<String> anas = (List<String>) pair.getValue();
            Collections.sort(anas, new LexComparator());
            result.add(anas);
        }
        
        return result;
        
    }
    
    class LexComparator implements Comparator<String> {
        @Override
        public int compare(String a, String b) {
            for (int i = 0; i < a.length(); i++) {
                if (a.charAt(i) < b.charAt(i)) {
                    return -1;
                } else if (a.charAt(i) > b.charAt(i)) {
                    return 1;
                }
            }
            
            return 0;
        }
    }
}