Anagrams are words or phrases that are formed by rearranging the letters of another word or phrase. In other words, an anagram is a word or phrase that contains the same letters with same frequency as another word or phrase, but in a different order.
For example, the word “listen” is an anagram of the word “silent”. This is because both words contain the same letters (e, i, l, n, s, t), but they are arranged in a different order. Another simple example is the word “debit” and “bited.” Both words contain the same letters (b, d, e, i, t), but they are arranged in a different order.
The key characteristic of anagrams is that the two words or phrases must contain the same letters with the same frequency. This means that if you count the number of times each letter appears in the first word, it must be the same as the number of times each corresponding letter appears in the second word.
Checking if Two Words Are Anagrams
To check if two words are anagrams, one simple method is to sort the letters in each word and then compare the sorted words. If the sorted words are identical, then the original words are anagrams.
For example, let’s take the words “listen” and “silent”. If we sort the letters in each word, we get:
“listen” -> “eilnst”
“silent” -> “eilnst”
Since the sorted words are the same, “listen” and “silent” are anagrams.
This method works because anagrams are words that have the same set of letters, just rearranged in a different order. By sorting the letters, we make the order consistent and so we can quickly compare the two words and determine if they are anagrams.
Grouping Anagrams Together
Grouping anagrams together means organizing a list of words into multiple sub-lists where all the words in each sub-list are anagrams of each other.
Here’s a small example:
Let’s say we have the following list of words:
- listen
- silent
- eat
- ate
- tea
- coffee
After grouping all the anagrams together, below is how it looks:
- listen, silent
- eat, ate, tea
- coffee
In this example, “listen” and “silent” are anagrams, as are “eat”, “ate” and “tea”. The word “coffee” is not an anagram of any other word in the list so no other word could be grouped as an anagram.
Brute Force Approach To Group Anagrams
The brute force approach to group anagrams is to sort each word and then compare it with all the other words in the list. If two words have the same sorted characters, they are anagrams and should be grouped together.
Algorithm
- Create a boolean array to keep track of whether a word has already been grouped or not.
- Iterate through the list of words.
- For each word, if the word is not already grouped, sort the characters in the word.
- Then, iterate through the remaining words in the list and check if the sorted characters match the current word.
- If a match is found, add the word to the group for the current word.
- Mark the matched word as grouped in the boolean array.
- Repeat steps 3-6 for all the words in the list.
Code
Time Complexity
The time complexity of the approach above is O(N^2 * KlogK), where N is the number of words and K is the average length of the words. Sorting each word takes (O(k log k)) and comparing each word with all other words takes (O(N^2)) time.
Space Complexity
The space complexity is O(N), as a boolean array is used to keep track of the grouped words. This space requirement is generally negligible when compared to the sizes of all the words.
This brute force approach is simple to implement, but it may not be efficient for large datasets, as the time complexity is quadratic. There are more efficient algorithms, such as the hash-based approach, which can achieve a time complexity of O(N * KlogK).
Optimal Approach Using Hash Maps To Group Anagrams
The brute force approach involves iterating through all upcoming words for each word. To make it more efficient, we can store the words in a hash map, where the sorted version of the word will be used as key, and the corresponding value will be a list of all the words that have the same sorted version. This approach requires a single pass through the data, making it more efficient.
Algorithm
Here’s a simple algorithm to group anagrams together using hash maps:
- Create an empty dictionary (hash map) to store the anagrams.
- Iterate through the list of words.
- For each word, create a sorted version of the word (e.g., “listen” becomes “eilnst”).
- Use the sorted version of the word as the key in the dictionary, and the original word as the value.
- If the key already exists in the dictionary, append the current word to the list of values.
- If the key does not exist in the dictionary, create a new list with the current word as the first element.
- After iterating through all the words, the dictionary will contain groups of anagrams, where the keys are the sorted versions of the words, and the values are lists of the original words.
- Return the values of the dictionary as the final result.
Code
Time Complexity
It takes O(N) time to iterate through all the words in the list and for each word, it takes Klog(K) time to sort each word. So the overall time complexity of this algorithm is O(N * Klog(K)), where N is the number of words and K is the length of the longest word.
Space Complexity
The space complexity is O(N * K), as we store all words in the input list into a hash map.