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
def group_anagrams(words):
# Create a boolean array to keep track of whether a word has already been grouped or not
is_grouped = [False for _ in words]
# Initialize an empty list to store the grouped anagrams
grouped_anagrams = []
# Iterate through the list of words
for i in range(len(words)):
# If the current word has not been grouped yet
if not is_grouped[i]:
# Create a list to store the current group of anagrams
current_group = []
# Add the current word to the group
current_group.append(words[i])
# Mark the current word as grouped
is_grouped[i] = True
# Sort the characters in the current word
sorted_word = ''.join(sorted(words[i]))
# Iterate through the remaining words in the list
for j in range(i + 1, len(words)):
# If the current word has not been grouped yet
if not is_grouped[j]:
# Sort the characters in the current word
sorted_other_word = ''.join(sorted(words[j]))
# If the sorted characters match, add the word to the current group
if sorted_word == sorted_other_word:
current_group.append(words[j])
# Mark the current word as grouped
is_grouped[j] = True
# Add the current group of anagrams to the list of grouped anagrams
grouped_anagrams.append(current_group)
# Return the list of grouped anagrams
return grouped_anagrams
# Lets now test the function
words = ["listen", "silent", "eat", "ate", "tea", "coffee"]
grouped_anagrams = group_anagrams(words)
print(grouped_anagrams)
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
// Function to group all anagrams together
std::vector<std::vector<std::string>> group_anagrams(std::vector<std::string>& words) {
// Create a boolean array to keep track of whether a word has already been grouped or not
std::vector<bool> is_grouped(words.size(), false);
// Initialize an empty list to store the grouped anagrams
std::vector<std::vector<std::string>> grouped_anagrams;
// Iterate through the list of words
for (int i = 0; i < words.size(); i++) {
// If the current word has not been grouped yet
if (!is_grouped[i]) {
// Create a list to store the current group of anagrams
std::vector<std::string> current_group;
// Add the current word to the group
current_group.push_back(words[i]);
// Mark the current word as grouped
is_grouped[i] = true;
// Sort the characters in the current word
std::string sorted_word = words[i];
std::sort(sorted_word.begin(), sorted_word.end());
// Iterate through the remaining words in the list
for (int j = i + 1; j < words.size(); j++) {
// If the current word has not been grouped yet
if (!is_grouped[j]) {
// Sort the characters in the current word
std::string sorted_other_word = words[j];
std::sort(sorted_other_word.begin(), sorted_other_word.end());
// If the sorted characters match, add the word to the current group
if (sorted_word == sorted_other_word) {
current_group.push_back(words[j]);
// Mark the current word as grouped
is_grouped[j] = true;
}
}
}
// Add the current group of anagrams to the list of grouped anagrams
grouped_anagrams.push_back(current_group);
}
}
// Return the list of grouped anagrams
return grouped_anagrams;
}
int main() {
std::vector<std::string> words = {"listen", "silent", "eat", "ate", "tea", "coffee"};
std::vector<std::vector<std::string>> grouped_anagrams = group_anagrams(words);
// Print the grouped anagrams
for (const auto& group : grouped_anagrams) {
for (const auto& word : group) {
std::cout << word << " ";
}
std::cout << std::endl;
}
return 0;
}
// Function to group all anagrams together
function groupAnagrams(words) {
// Create a boolean array to keep track of whether a word has already been grouped or not
const isGrouped = new Array(words.length).fill(false);
// Initialize an empty list to store the grouped anagrams
const groupedAnagrams = [];
// Iterate through the list of words
for (let i = 0; i < words.length; i++) {
// If the current word has not been grouped yet
if (!isGrouped[i]) {
// Create a list to store the current group of anagrams
const currentGroup = [];
// Add the current word to the group
currentGroup.push(words[i]);
// Mark the current word as grouped
isGrouped[i] = true;
// Sort the characters in the current word
const sortedWord = words[i].split('').sort().join('');
// Iterate through the remaining words in the list
for (let j = i + 1; j < words.length; j++) {
// If the current word has not been grouped yet
if (!isGrouped[j]) {
// Sort the characters in the current word
const sortedOtherWord = words[j].split('').sort().join('');
// If the sorted characters match, add the word to the current group
if (sortedWord === sortedOtherWord) {
currentGroup.push(words[j]);
// Mark the current word as grouped
isGrouped[j] = true;
}
}
}
// Add the current group of anagrams to the list of grouped anagrams
groupedAnagrams.push(currentGroup);
}
}
// Return the list of grouped anagrams
return groupedAnagrams;
}
// Lets now test the function
const words = ['listen', 'silent', 'eat', 'ate', 'tea', 'coffee'];
const groupedAnagrams = groupAnagrams(words);
console.log(groupedAnagrams);
import java.util.*;
public class Main {
// Function to group all anagrams together
public static List<List<String>> groupAnagrams(String[] words) {
// Create a boolean array to keep track of whether a word has already been grouped or not
boolean[] isGrouped = new boolean[words.length];
// Initialize an empty list to store the grouped anagrams
List<List<String>> groupedAnagrams = new ArrayList<>();
// Iterate through the list of words
for (int i = 0; i < words.length; i++) {
// If the current word has not been grouped yet
if (!isGrouped[i]) {
// Create a list to store the current group of anagrams
List<String> currentGroup = new ArrayList<>();
// Add the current word to the group
currentGroup.add(words[i]);
// Mark the current word as grouped
isGrouped[i] = true;
// Sort the characters in the current word
char[] sortedWord = words[i].toCharArray();
Arrays.sort(sortedWord);
// Iterate through the remaining words in the list
for (int j = i + 1; j < words.length; j++) {
// If the current word has not been grouped yet
if (!isGrouped[j]) {
// Sort the characters in the current word
char[] sortedOtherWord = words[j].toCharArray();
Arrays.sort(sortedOtherWord);
// If the sorted characters match, add the word to the current group
if (Arrays.equals(sortedWord, sortedOtherWord)) {
currentGroup.add(words[j]);
// Mark the current word as grouped
isGrouped[j] = true;
}
}
}
// Add the current group of anagrams to the list of grouped anagrams
groupedAnagrams.add(currentGroup);
}
}
// Return the list of grouped anagrams
return groupedAnagrams;
}
public static void main(String[] args) {
String[] words = {"listen", "silent", "eat", "ate", "tea", "coffee"};
List<List<String>> groupedAnagrams = groupAnagrams(words);
System.out.println(groupedAnagrams);
}
}
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
# Function to group all anagrams together
def group_anagrams(words):
# Create an empty dictionary to store the anagrams
anagram_dict = {}
# Iterate through the list of words
for word in words:
# Create a sorted version of the word
sorted_word = ''.join(sorted(word))
# Check if the sorted version of the word is already in the dictionary
if sorted_word in anagram_dict:
# If it is, append the current word to the list of values
anagram_dict[sorted_word].append(word)
else:
# If it's not, create a new list with the current word as the first element
anagram_dict[sorted_word] = [word]
# Return the values of the dictionary as the final result
return list(anagram_dict.values())
# Lets now test the function
words = ["listen", "silent", "eat", "ate", "tea", "coffee"]
grouped_anagrams = group_anagrams(words)
print(grouped_anagrams)
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <string>
// Function to group all anagrams together
std::vector<std::vector<std::string>> groupAnagrams(std::vector<std::string>& words) {
// Create an empty dictionary to store the anagrams
std::unordered_map<std::string, std::vector<std::string>> anagramDict;
// Iterate through the list of words
for (const auto& word : words) {
// Create a sorted version of the word
std::string sortedWord = word;
std::sort(sortedWord.begin(), sortedWord.end());
// Check if the sorted version of the word is already in the dictionary
if (anagramDict.count(sortedWord)) {
// If it is, append the current word to the list of values
anagramDict[sortedWord].push_back(word);
} else {
// If it's not, create a new list with the current word as the first element
anagramDict[sortedWord] = {word};
}
}
// Return the values of the dictionary as the final result
std::vector<std::vector<std::string>> result;
for (const auto& pair : anagramDict) {
result.push_back(pair.second);
}
return result;
}
int main() {
std::vector<std::string> words = {"listen", "silent", "eat", "ate", "tea", "coffee"};
std::vector<std::vector<std::string>> groupedAnagrams = groupAnagrams(words);
for (const auto& group : groupedAnagrams) {
for (const auto& word : group) {
std::cout << word << " ";
}
std::cout << std::endl;
}
return 0;
}
// Function to group all anagrams together
function groupAnagrams(words) {
// Create an empty dictionary to store the anagrams
const anagramDict = {};
// Iterate through the list of words
for (const word of words) {
// Create a sorted version of the word
const sortedWord = word.split('').sort().join('');
// Check if the sorted version of the word is already in the dictionary
if (anagramDict[sortedWord]) {
// If it is, append the current word to the list of values
anagramDict[sortedWord].push(word);
} else {
// If it's not, create a new list with the current word as the first element
anagramDict[sortedWord] = [word];
}
}
// Return the values of the dictionary as the final result
return Object.values(anagramDict);
}
// Lets now test the function
const words = ['listen', 'silent', 'eat', 'ate', 'tea', 'coffee'];
const groupedAnagrams = groupAnagrams(words);
console.log(groupedAnagrams);
import java.util.*;
public class Main {
// Function to group all anagrams together
public static List<List<String>> groupAnagrams(String[] words) {
// Create an empty dictionary to store the anagrams
Map<String, List<String>> anagramDict = new HashMap<>();
// Iterate through the list of words
for (String word : words) {
// Create a sorted version of the word
char[] charArray = word.toCharArray();
Arrays.sort(charArray);
String sortedWord = new String(charArray);
// Check if the sorted version of the word is already in the dictionary
if (anagramDict.containsKey(sortedWord)) {
// If it is, append the current word to the list of values
anagramDict.get(sortedWord).add(word);
} else {
// If it's not, create a new list with the current word as the first element
List<String> anagramList = new ArrayList<>();
anagramList.add(word);
anagramDict.put(sortedWord, anagramList);
}
}
// Return the values of the dictionary as the final result
return new ArrayList<>(anagramDict.values());
}
public static void main(String[] args) {
String[] words = {"listen", "silent", "eat", "ate", "tea", "coffee"};
List<List<String>> groupedAnagrams = groupAnagrams(words);
System.out.println(groupedAnagrams);
}
}
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.