Group Anagrams

Lecture 76 :- Group Anagrams

Grouping anagrams is a common problem in computer science and involves categorizing words or strings that are anagrams of each other into distinct groups. Anagrams are words or phrases formed by rearranging the letters of another word or phrase, using all the original letters exactly once.

For example, "listen," "silent," and "enlist" are anagrams because they all use the same letters.

To group anagrams efficiently, you can use a hash table or a dictionary-like data structure to keep track of the groups. Here's a step-by-step algorithm to group anagrams:

Create a dictionary (hash table) where the keys will be sorted versions of the words, and the values will be lists of words that are anagrams of each other.

Iterate through each word in the list of words.

For each word, sort its characters in alphabetical order and use the sorted version as the key to the dictionary.

If the sorted version is already a key in the dictionary, append the current word to the corresponding list of anagrams.

If the sorted version is not a key in the dictionary, create a new entry with the sorted version as the key and a list containing only the current word.

After processing all the words, the dictionary will contain groups of anagrams.

Return the lists of anagrams as the final result.

Here's a Python function that implements this algorithm:

pythonCopy code

def group_anagrams(words):    anagram_groups = {}    for word in words:        sorted_word = ''.join(sorted(word))        if sorted_word in anagram_groups:            anagram_groups[sorted_word].append(word)        else:            anagram_groups[sorted_word] = [word]        return list(anagram_groups.values()) # Example usage: words = ["listen", "silent", "enlist", "arc", "car", "rat", "tar", "act", "cat"] result = group_anagrams(words) print(result)

Output:

cssCopy code

[['listen', 'silent', 'enlist'], ['arc', 'car'], ['rat', 'tar'], ['act', 'cat']]

The function will return a list of lists, where each inner list contains words that are anagrams of each other. In this example, the words "listen," "silent," and "enlist" are grouped together as they are anagrams of one another. The same goes for "arc" and "car," as well as "rat" and "tar," and "act" and "cat."