Group Anagrams
Group words that are anagrams. Sort words within each group alphabetically, then sort groups by their first word.
Work through the cases
3 examplesInput notation
Space-separated lowercase words.Expected result
One group per line, with words separated by spaces.Case 1
Input
eat tea tan ate nat bat
Expected output
ate eat tea bat nat tan
Case 2
Input
ab ba a
Expected output
a ab ba
Case 3
Input
z z
Expected output
z z
These notes use simplified input/output notation. The linked platform defines the method signature and judge format.
FROM IDEA TO IMPLEMENTATION
Understand the approach.
Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.
The first idea is pairwise anagram checks: sort each string and compare. Correct, but n ≤ 10^4 and k ≤ 100 make O(n^2 × k log k) too slow. Pairwise comparison is the bottleneck. Anagrams share one sorted form — that string is the group id. Use the sorted string as key and a list of originals as value. One pass into a hash table clusters them; no pairwise matching.
1. Traverse the string array, sort each string in character dictionary order to get a new string. 2. Use the new string as key and [str] as value, and store them in the hash table (HashMap<String, List>). 3. When encountering the same key during subsequent traversal, add it to the corresponding value.
Take strs = ["eat", "tea", "tan", "ate", "nat", "bat"] as an example. At the end of the traversal, the state of the hash table is:
| key | value | | ------- | ----------------------- | | "aet" | ["eat", "tea", "ate"] | | "ant" | ["tan", "nat"] | | "abt" | ["bat"] |
Finally, return the value list of the hash table.
The time complexity is O(n × k × log k), where n and k are the lengths of the string array and the maximum length of the string, respectively.
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> d = new HashMap<>();
for (String s : strs) {
char[] t = s.toCharArray();
Arrays.sort(t);
String k = String.valueOf(t);
d.computeIfAbsent(k, key -> new ArrayList<>()).add(s);
}
return new ArrayList<>(d.values());
}
}Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.
Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.