Lintcode: Anagrams

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

Have you met this question in a real interview? 

Yes

Example

Given ["lint", "intl", "inlt", "code"], return ["lint", "inlt", "intl"].

Given ["ab", "ba", "cd", "dc", "e"], return ["ab", "ba", "cd", "dc"].

Note

All inputs will be in lower-case

Tags Expand 

String Hash Table

Create a hashmap: key is the sorted input string, value is a vector containing strings.

Scan the whole hash map, output the values where key corresponds to more than one string.
The condition that all inputs will be in lower-case helps to get key by sort().

Good analysis of complexity
Time complexity: Sort:O(mlogm)*n + Comparison:O(n) = O(nmlogm)    
Space complexity: O(nm)
p.s. m is the longest length of string in strs while n is the number of strings in strs.

 Codes reference: http://bangbingsyb.blogspot.com/2014/11/leetcode-anagrams.html

class Solution {
public:    
    /**
     * @param strs: A list of strings
     * @return: A list of strings
     */
    vector<string> anagrams(vector<string> &strs) {
        // write your code here
        unordered_map<string, vector<string> > map;
        vector<string> result;
        for(string s: strs){
            string key = s;
            sort(key.begin(), key.end());
            map[key].push_back(s);
        }
        for(auto it = map.begin(); it != map.end(); it++){
            if(it->second.size() > 1){
                for(int i = 0; i < it->second.size(); i++){
                    result.push_back(it->second[i]);
                }
            } 
        }
        return result;
    }
};