Problem description:

Given an array of strings, group anagrams together.

Example:

1
2
3
4
5
6
7
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.

Solution:

The idea is to use an unordered_map to store those strings that are anagrams. We use the sorted string as the key and the string itself as the value. The strings are stored in a multiset since there may be duplicates. Moreover, multiset will sort them by default as we desire.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        
        unordered_map<string, multiset<string>> map;
        for(auto s: strs){
            string tmp = s; 
            sort(tmp.begin(), tmp.end());  //use the sorted string as key to store every similar strings
            map[tmp].insert(s);
        }
        
        vector<vector<string>> res;
        for(auto m: map){
            vector<string> tmp(m.second.begin(), m.second.end());
            res.push_back(tmp);
        }
        return res;
    }
};

time complexity: O(nlogn)

Second time:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # Use a hash map, and sort the different words in order to compare them.
        # You can only use immutable types as a key in a hash map, so we use tuples as keys.
        # Tuples are just an immutable collection of items, basically an immutable list.
        # Doing tuple(sorted(word)) returns a list of letters sorted alphabetically, ex:
        # word = "eat"
        # sorted(word) = ['a', 'e', 't']
        # tuple(sorted(word)) = ('a', 'e', 't')
        group = {}
        
        for word in strs:
            # Make the word tuple the key, and a list of words as the value.
            key = tuple(sorted(word))
            
            # Here, the [] parameter in the .get function is an optional value to return if the specified
            # key does not exist. It safeguards if we try to add a value to a key that's not in the map yet.
            group[key] = group.get(key, []) + [word]
            # print(type(key)) (a tuple)
            # print(type(group[key])) (a list)
            
        # More explanation of the above:
        # Sort the current word, make it a tuple, and use it as a key.
        # Add the un-sorted word as the value for that key.
        # Since keys are unique in maps, next time you sort a word and get the same tuple,
        # just add/concatenate the un-sorted word to the value of the existing key, making it a list.
        
        # A note about list.append() vs the + operator on lists:
        # .append() modifies an existing list, mutating it. It doesn't return anything. (newList = oldList.append(3) fails)
        # The + operator concatenates two lists and returns a new one.
        
        # Returns a list of all the values in the map. So, a list of lists
        return group.values()