Group anagrams
Medium TimeO(n·k log k) SpaceO(n·k)
Given an array of words, group together those that are anagrams of one another — the same characters in the same quantities, in any order — and return the groups as an array of arrays. Every word belongs to exactly one group, a word with no anagram among the others forms a group of one, and the order of the groups does not matter.
Examples
Example 1
- Input
- words = ["eat", "tea", "tan", "ate", "nat", "bat"]
- Output
[["eat","tea","ate"],["tan","nat"],["bat"]]eat,teaandateuse the same three letters,tanandnatthe same three, andbatshares with neither.
Example 2
- Input
- words = ["abc", "bca", "xyz"]
- Output
- The first two both sort to
[["abc","bca"],["xyz"]]"abc";"xyz"sorts to itself and is alone.
The Code
function groupAnagrams(words) {
const groups = {};
for (let i = 0; i < words.length; i++) {
const key = words[i].split("").sort().join("");
if (groups[key] === undefined) groups[key] = [];
groups[key].push(words[i]);
}
return Object.keys(groups).map((k) => groups[k]);
}
groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]);Done
More like this
All strings examples (13) →- Reverse words Split on whitespace, walk backwards, join again.
- Valid anagram Count letters up with one word, down with the other.
- Common prefix Start with the whole first word, shrink until everything matches.
- Run-length encoding Collapse each run of repeats into a character and a count.
- First unique char Count every character first, then find the earliest with count 1.
- Longest unique substring A sliding window that jumps forward past any repeat.