Group Anagrams
Given an array of strings, group the anagrams together. You can return the answer in any order. An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Constraints:
- 1 <= strs.length <= 10^4
- 0 <= strs[i].length <= 100
- strs[i] consists of lowercase English letters.
Examples:
Input: ["eat","tea","tan","ate","nat","bat"]
Output: [["eat","tea","ate"],["tan","nat"],["bat"]]
Explanation: The anagrams are: "eat", "tea", and "ate" are anagrams; "tan" and "nat" are anagrams; "bat" has no anagrams.
Solutions
Hash Table
We use a hash table to store the anagrams. The key is the sorted version of the string, and the value is a list of strings that are anagrams of the key. We iterate through the input array, sort each string, and use the sorted string as the key in the hash table. If the key is not in the hash table, we add it with an empty list as the value. Then we append the original string to the list of the corresponding key. Finally, we return the values of the hash table, which are the groups of anagrams.
const groupAnagrams = (strs) => {
const map = {};
for (const str of strs) {
const sortedStr = str.split('').sort().join('');
if (!map[sortedStr]) map[sortedStr] = [];
map[sortedStr].push(str);
}
return Object.values(map);
};
Follow-up:
What if the input array is very large and we want to group the anagrams in a streaming fashion?
