Practice/Amazon/Leetcode 49. Group Anagrams

Leetcode 49. Group Anagrams

CodingMust

Problem

Given an array of strings, organize them into clusters where each cluster contains words that have identical letter compositions. Two words belong to the same cluster if they contain exactly the same letters with the same frequencies, regardless of order.

Return the clusters in any order. The words within each cluster can also appear in any order.

Requirements

1. Group words that contain identical multisets of characters
2. Each word should appear in exactly one cluster
3. Return all clusters as a list of lists
4. The order of clusters and words within clusters does not matter

Constraints

• 0 <= words.length <= 10000
• 0 <= words[i].length <= 100
• words[i] consists of lowercase English letters only
• Your solution should handle empty strings and empty arrays
• Time complexity should be O(n * k) where n is the number of words and k is the maximum length of a word
• Space complexity should be O(n * k) for storing the results and intermediate data structures

Examples

Example 1:

` Input: words = ["eat", "tea", "tan", "ate", "nat", "bat"] Output: [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]] Explanation:

• "eat", "tea", and "ate" all contain the letters {e, a, t}
• "tan" and "nat" both contain the letters {t, a, n}
• "bat" is unique with letters {b, a, t} `

Example 2:

Input: words = [""] Output: [[""]] Explanation: An empty string forms its own cluster

Example 3:

Input: words = ["a"] Output: [["a"]] Explanation: A single word forms a single cluster

Example 4:

Input: words = ["listen", "silent", "enlist"] Output: [["listen", "silent", "enlist"]] Explanation: All three words contain the same letters with identical frequencies