πDay 7. Print Anagrams Together π§
The problem can be found at the following link: Problem Link
π‘ Problem Description:
You are given an array arr[]
of strings. Your task is to group the anagrams together and return all such groups. The groups must be created in order of their appearance in the original array.
Note: The final output will be in lexicographic order.
π Example Walkthrough:
Input:
arr[] = ["act", "god", "cat", "dog", "tac"]
Output:
[["act", "cat", "tac"], ["god", "dog"]]
Explanation:
There are 2 groups of anagrams:
"god", "dog" make group 1
"act", "cat", "tac" make group 2
Input:
arr[] = ["no", "on", "is"]
Output:
[["is"], ["no", "on"]]
Explanation:
There are 2 groups of anagrams:
"is" makes group 1
"no", "on" make group 2
Input:
arr[] = ["listen", "silent", "enlist", "abc", "cab", "bac", "rat", "tar", "art"]
Output:
[["abc", "cab", "bac"], ["listen", "silent", "enlist"], ["rat", "tar", "art"]]
Explanation:
Group 1: "abc", "bac", and "cab" are anagrams.
Group 2: "listen", "silent", and "enlist" are anagrams.
Group 3: "rat", "tar", and "art" are anagrams.
Constraints:
1 <= arr.size() <= 100
1 <= arr[i].size() <= 10
π― My Approach:
Sorting-Based Grouping:
An anagram is a word formed by rearranging the letters of another word. Hence, for grouping anagrams, we can sort each string and use the sorted version as the key in a map (unordered_map).
The key idea is that anagrams, when sorted, will produce the same string. For example, "act", "cat", and "tac" will all produce "act" when sorted.
Steps:
Create a hashmap (unordered_map) where the key is the sorted string and the value is a list of anagrams corresponding to that key.
For each string in the array, sort it, and add the original string to the list of the corresponding key in the map.
After processing all strings, return the values of the hashmap as a list of anagram groups.
π Time and Auxiliary Space Complexity
Expected Time Complexity: O(n _ m _ log(m)), where
n
is the number of strings andm
is the maximum length of any string. Sorting each string takes O(m * log(m)), and we do this for alln
strings.Expected Auxiliary Space Complexity: O(n * m), where
n
is the number of strings andm
is the maximum length of any string. The space is used for the hashmap and the output list.
π Solution Code
Code (C++)
class Solution {
public:
vector<vector<string>> anagrams(vector<string>& arr) {
unordered_map<string, vector<string>> umap;
for (const string& s : arr) {
string sorted_s = s;
sort(sorted_s.begin(), sorted_s.end());
umap[sorted_s].push_back(s);
}
vector<vector<string>> result;
for (auto it = umap.begin(); it != umap.end(); ++it)
result.push_back(move(it->second));
return result;
}
};
Code (Java)
class Solution {
public ArrayList<ArrayList<String>> anagrams(String[] arr) {
Map<String, ArrayList<String>> umap = new HashMap<>();
for (String s : arr) {
char[] chars = s.toCharArray();
Arrays.sort(chars);
String sorted_s = new String(chars);
umap.computeIfAbsent(sorted_s, k -> new ArrayList<>()).add(s);
}
ArrayList<ArrayList<String>> result = new ArrayList<>(umap.values());
return result;
}
}
Code (Python)
from collections import defaultdict
class Solution:
def anagrams(self, arr):
umap = defaultdict(list)
for s in arr:
sorted_s = ''.join(sorted(s))
umap[sorted_s].append(s)
return list(umap.values())
π― Contribution and Support:
For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Letβs make this learning journey more collaborative!
β If you find this helpful, please give this repository a star! β
πVisitor Count
Last updated