Given a sequence of words, print all anagrams together
Problem Statement
Given a sequence of words, print all anagrams together. Two words are anagrams if they contain the same characters with the same frequencies, just rearranged.
Example:
Input: ["cat", "dog", "tac", "god", "act"]
Output: [["cat", "tac", "act"], ["dog", "god"]]
Explanation:
- "cat", "tac", "act" are anagrams of each other
- "dog", "god" are anagrams of each other
Noob-Friendly Explanation
Imagine you have a bag of Scrabble tiles for each word. Two words are anagrams if their bags contain the exact same tiles.
For example, "cat" has tiles {c, a, t} and "tac" also has tiles {t, a, c} — same tiles, just arranged differently. But "cat" and "dog" have completely different tiles.
The trick is: if you sort the letters of any word, all its anagrams will produce the same sorted string. "cat" → "act", "tac" → "act", "act" → "act". They all become "act"! So we can use this sorted version as a key to group anagrams together.
We use a Trie to store these sorted keys efficiently.
Approach 1: Brute Force
Intuition
For each pair of words, check if they are anagrams by comparing character frequencies. Group words that are anagrams of each other.
Algorithm
- For each word, compare it with every other word
- Two words are anagrams if they have the same character frequency
- Use a visited array to avoid processing the same word twice
- Group all matching words together
import java.util.*;
class Solution {
private static boolean areAnagrams(String s1, String s2) {
if (s1.length() != s2.length()) return false;
int[] freq = new int[26];
for (char c : s1.toCharArray()) freq[c - 'a']++;
for (char c : s2.toCharArray()) freq[c - 'a']--;
for (int f : freq) {
if (f != 0) return false;
}
return true;
}
public static List<List<String>> groupAnagrams(String[] words) {
int n = words.length;
boolean[] visited = new boolean[n];
List<List<String>> result = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (visited[i]) continue;
List<String> group = new ArrayList<>();
group.add(words[i]);
visited[i] = true;
for (int j = i + 1; j < n; j++) {
if (!visited[j] && areAnagrams(words[i], words[j])) {
group.add(words[j]);
visited[j] = true;
}
}
result.add(group);
}
return result;
}
public static void main(String[] args) {
String[] words = {"cat", "dog", "tac", "god", "act"};
List<List<String>> result = groupAnagrams(words);
for (List<String> group : result) {
System.out.println(group);
}
// [cat, tac, act]
// [dog, god]
}
}Complexity Analysis
- Time Complexity: O(N^2 * L) — Compare each pair of N words, each comparison takes O(L)
- Space Complexity: O(N * L) — Storing the groups
Approach 2: Optimal (Trie with Sorted Keys)
Intuition
Sort each word's characters to create a canonical form. All anagrams produce the same sorted string. Insert these sorted strings into a Trie, and at each end-of-word node, store the list of original words that map to that sorted key.
Algorithm
- For each word, sort its characters to get the key (e.g., "cat" → "act")
- Insert the sorted key into a Trie
- At the leaf node, maintain a list of original words
- Traverse the Trie and collect all groups
import java.util.*;
class Solution {
static class TrieNode {
TrieNode[] children;
List<String> words; // words whose sorted form passes through here
public TrieNode() {
children = new TrieNode[26];
words = null;
}
}
private static TrieNode root;
private static void insert(String sortedKey, String originalWord) {
TrieNode current = root;
for (int i = 0; i < sortedKey.length(); i++) {
int index = sortedKey.charAt(i) - 'a';
if (current.children[index] == null) {
current.children[index] = new TrieNode();
}
current = current.children[index];
}
if (current.words == null) {
current.words = new ArrayList<>();
}
current.words.add(originalWord);
}
private static void collectGroups(TrieNode node, List<List<String>> result) {
if (node == null) return;
if (node.words != null && !node.words.isEmpty()) {
result.add(node.words);
}
for (int i = 0; i < 26; i++) {
collectGroups(node.children[i], result);
}
}
public static List<List<String>> groupAnagrams(String[] words) {
root = new TrieNode();
for (String word : words) {
char[] chars = word.toCharArray();
Arrays.sort(chars);
String sortedKey = new String(chars);
insert(sortedKey, word);
}
List<List<String>> result = new ArrayList<>();
collectGroups(root, result);
return result;
}
public static void main(String[] args) {
String[] words = {"cat", "dog", "tac", "god", "act"};
List<List<String>> result = groupAnagrams(words);
for (List<String> group : result) {
System.out.println(group);
}
// [cat, tac, act]
// [dog, god]
}
}Complexity Analysis
- Time Complexity: O(N * L * log(L)) — Sorting each word takes O(L * log(L)), done for N words
- Space Complexity: O(N * L) — Trie nodes and stored words
Key Takeaways
- Sorted Key Trick: Sorting characters of a word gives a canonical form — all anagrams share the same sorted form
- Trie as a Grouping Tool: Instead of a HashMap, a Trie can group words by their sorted keys
- HashMap Alternative: In practice, using
HashMap<String, List<String>>with sorted keys is equally efficient. Trie shines when you need prefix-based lookups - Real-world Use: Search engines group anagrams to improve search results