grid47 Exploring patterns and algorithms
Nov 2, 2024
6 min read
Solution to LeetCode 49: Group Anagrams Problem
You are given an array of strings. Group the strings that are anagrams of each other together and return them as a list of lists. An anagram is a word or phrase formed by rearranging the letters of another word or phrase.
Problem
Approach
Steps
Complexity
Input: The input is an array of strings, where each string is a lowercase English word.
• Explanation: In this example, the strings "listen", "silent", and "enlist" form one group of anagrams, while "rat", "tar", and "art" form another group.
• Input: ["cat", "dog", "god", "act"]
• Explanation: Here, "cat" and "act" are anagrams of each other, while "dog" and "god" form a separate group.
Approach: The approach involves using a map to group the strings that are anagrams of each other based on a unique signature (e.g., sorted characters or character count).
Observations:
• Anagrams can be identified by sorting the characters in the string or by using a frequency count of characters.
• Using a frequency count or sorted string as a key in a map can efficiently group the anagrams.
Steps:
• 1. Create a map to store groups of anagrams.
• 2. For each string, generate a unique signature (e.g., sorted version of the string or a frequency count of characters).
• 3. Use this signature as the key in the map and add the string to the corresponding list of anagrams.
• 4. After processing all strings, return the values from the map, which are the grouped anagrams.
Empty Inputs:
• If the input contains an empty string, it should be grouped separately.
Large Inputs:
• For larger inputs, the algorithm should still efficiently group anagrams within the constraints.
Special Values:
• Anagrams with only one character should be grouped together.
Constraints:
• The input strings contain only lowercase letters and have lengths between 0 and 100.
This line declares a function named `code` that takes a string `x` as input and returns a string representing the character frequency of the input string.
2 : Array Initialization
vector<int> q(26, 0);
This line initializes a vector `q` of size 26 to store the frequency of each lowercase letter.
3 : Character Frequency Calculation
for(int i =0; i < x.size(); i++) {
This loop iterates over each character in the input string `x`.
4 : Character Frequency Calculation
q[x[i] -'a']++;
The frequency of the current character `x[i]` is incremented in the corresponding index of the `q` vector.
5 : String Stream Initialization
stringstream ss;
A string stream `ss` is initialized to construct the character frequency string.
6 : String Stream Manipulation
for(int i =0; i <26; i++) {
This loop iterates over the frequency array `q`.
7 : String Stream Manipulation
if(i !=0) ss <<',';
If it's not the first iteration, a comma is added to the string stream as a separator.
8 : String Stream Manipulation
ss << q[i];
The frequency of the current character is appended to the string stream.
9 : Return Frequency String
return ss.str();
The final string representation of the character frequencies is returned.
This line declares the main function `groupAnagrams` that takes a vector of strings `strs` as input and returns a vector of vectors containing grouped anagrams.
11 : Map Initialization
map<string, vector<string>> ma;
A map `ma` is initialized to store the character frequency string as the key and a vector of anagrams as the value.
12 : Iterate Over Strings
for(string x: strs) {
This loop iterates over each string `x` in the input vector `strs`.
13 : Generate Character Frequency String
string mask = code(x);
The `code` function is called to generate the character frequency string `mask` for the current string `x`.
14 : Group Anagrams
ma[mask].push_back(x);
The current string `x` is added to the vector of anagrams associated with the `mask` key in the `ma` map.
15 : Result Vector Initialization
vector<vector<string>> ans;
A 2D vector `ans` is initialized to store the grouped anagrams.
16 : Populate Result Vector
for(auto [key, val]: ma)
This loop iterates over the key-value pairs in the `ma` map.
17 : Populate Result Vector
ans.push_back(val);
The vector of anagrams associated with the current key is added to the `ans` vector.
18 : Return Result
return ans;
The `ans` vector containing the grouped anagrams is returned.
Best Case: O(n * k log k)
Average Case: O(n * k log k)
Worst Case: O(n * k log k)
Description: The time complexity is O(n * k log k), where n is the number of strings and k is the length of the longest string. Sorting each string takes O(k log k) time.
Best Case: O(n)
Worst Case: O(n * k)
Description: The space complexity is O(n * k) where n is the number of strings and k is the average length of the strings, due to the space used by the map to store the anagram groups.
