Medium
Subtopics
array·hash-table·sorting·string
Companies
adobe·affirm·amazon·apple·bloomberg·bookingcom·cisco·docusign·ebay·electronic-arts·facebook·goldman-sachs·google·hulu·intuit·mathworks·microsoft·nutanix·oracle·qualtrics·salesforce·servicenow·snapchat·tesla·twilio·uber·visa·vmware·wish·yahoo·yandex·yelp·zulilyLast updated: Aug 2, 2025
For example, suppose that we have the following strings:
Example 1:
1
2
3
4
5
6
Input: strs =["eat","tea","tan","ate","nat","bat"]Output:[["bat"],["nat","tan"],["ate","eat","tea"]]Explanation:
There is no string in strs that can be rearranged to form "bat".The strings "nat" and "tan" are anagrams as they can be rearranged to form each other.The strings "ate","eat", and "tea" are anagrams as they can be rearranged to form each other.
One straightforward approach is to construct a Hash Table. Compute hash values for each word such that anagrams yield identical hash values. Populate the Hash Table with these values. However, devising an appropriate hash function can be challenging. Instead, consider the following method that utilizes a count array.
classSolution {
staticclassTrie {
staticclassTrieNode {
privateboolean isLeaf;
private TrieNode[] children =new TrieNode[26];
private List<String> words =new ArrayList<>(); // Store words at the leaf nodes }
private TrieNode root;
/** Initialize the Trie. */publicTrie() {
this.root=new TrieNode();
}
/** Inserts a word into the trie. */publicvoidinsert(String word, String originalWord) {
TrieNode curr =this.root;
for (char c : word.toCharArray()) {
int idx = c -'a';
if (curr.children[idx]==null) {
curr.children[idx]=new TrieNode();
}
curr = curr.children[idx];
}
curr.isLeaf=true;
curr.words.add(
originalWord); // Add the original word at the leaf node }
// Function to traverse the Trie and collect all anagramspublicvoidcollectAnagrams(TrieNode node, List<List<String>> result) {
if (node ==null)
return;
if (node.isLeaf) {
result.add(new ArrayList<>(node.words));
}
for (TrieNode child : node.children) {
if (child !=null) {
collectAnagrams(child, result);
}
}
}
}
public List<List<String>>groupAnagrams(String[] strs) {
if (strs ==null|| strs.length== 0) {
returnnew ArrayList<>();
}
Trie trie =new Trie();
for (String s : strs) {
char[] charArray = s.toCharArray();)
Arrays.sort(charArray);
String sortedWord =new String(charArray);
trie.insert(sortedWord, s);
}
List<List<String>> ans =new ArrayList<>();
collectAnagrams(this.root, ans);
return ans;
}
}