Blind 75
Solution: Group Anagrams
Problem Statement
Given a list of strings, the task is to group the anagrams together.
An anagram is a word or phrase formed by rearranging the letters of another, such as "cinema", formed from "iceman"
You can return the answer in any order.
Examples
Example 1:
- Input:
["dog", "god", "hello"]
- Output:
[["dog", "god"], ["hello"]]
- Justification: "dog" and "god" are anagrams, so they are grouped together. "hello" does not have any anagrams in the list, so it is in its own group.
Example 2:
- Input:
["listen", "silent", "enlist"]
- Output:
[["listen", "silent", "enlist"]]
- Justification: All three words are anagrams of each other, so they are grouped together.
Example 3:
- Input:
["abc", "cab", "bca", "xyz", "zxy"]
- Output:
[["abc", "cab", "bca"], ["xyz", "zxy"]]
- Justification: "abc", "cab", and "bca" are anagrams, as are "xyz" and "zxy".
Constraints:
- 1 <= strs.length <= 10<sup>4</sup>
0 <= strs[i].length <= 100
strs[i]
consists of lowercase English letters.
Solution
-
Sorting Approach:
- For each word in the input list:
- Sort the letters of the word.
- Use the sorted word as a key in a hash map, and add the original word to the list of values for that key.
- The hash map values will be the groups of anagrams.
- For each word in the input list:
-
Why This Will Work:
- Anagrams will always result in the same sorted word, so they will be grouped together in the hash map.
Algorithm Walkthrough
- Given the input
["abc", "cab", "bca", "xyz", "zxy"]
- For "abc":
- Sorted word is "abc".
- Add "abc" to the hash map with key "abc".
- For "cab":
- Sorted word is "abc".
- Add "cab" to the list in the hash map with key "abc".
- Continue this process for all words.
- The hash map values are the groups of anagrams.
Code
Python3
Python3
Complexity Analysis
- Time Complexity: O(n*k*log(k)), where n is the number of strings, and k is the maximum length of a string in strs. This is because each of the n strings is sorted in O(k*log(k)) time.
- Space Complexity: O(n*k), where n is the number of strings, and k is the maximum length of a string in strs. This space is used for the output data structure and the hash map.