anagram using vector

leo2008 (148)
I am trying to solve this problem. Are there any other better approaches here?

Implement a function which takes a list of words as an argument and finds all anagrams within the list. Anagrams are words which contain the exact same letters, like CREATED/CATERED/REACTED.

Create a vector for each group of 2 or more anagrams, then return the vector of all groups. You can put the results in any order.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 
 #include <iostream> #include <vector> #include <unordered_map> #include <algorithm> std::vector<std::vector<std::string>> findAnagrams(const std::vector<std::string>& words) { std::unordered_map<std::string, std::vector<std::string>> anagramGroups; // Firstly Group words by their sorted version for (const std::string& word : words) { // Create a sorted version of the word (this is the key for anagram groups) std::string sortedWord = word; std::sort(sortedWord.begin(), sortedWord.end()); // Add the original word to the group with the corresponding sorted key anagramGroups[sortedWord].push_back(word); } // Now Collect all anagram groups that have more than one word std::vector<std::vector<std::string>> result; for (const auto& entry : anagramGroups) { if (entry.second.size() > 1) { result.push_back(entry.second); } } return result; } int main() { std::vector<std::string> words = {"created", "catered", "reacted", "dog", "god", "act", "cat", "tac"}; // Find anagram groups std::vector<std::vector<std::string>> anagramGroups = findAnagrams(words); // Print the result for (const auto& group : anagramGroups) { for (const auto& word : group) { std::cout << word << " "; } std::cout << std::endl; } return 0; } Output: act cat tac dog god created catered reacted
Last edited on
seeplus (6639)
1
2
3
4
5
 
for (const std::string& word : words) { // Create a sorted version of the word (this is the key for anagram groups) std::string sortedWord = word; std::sort(sortedWord.begin(), sortedWord.end());


If you don't use word by ref you don't need the assignment statement:

1
2
3
4
 
for (auto word : words) { // Create a sorted version of the word (this is the key for anagram groups) std::sort(word.begin(), word.end());

jonnin (11497)
If you go big (a large dictionary of words) you may want to move out to a hash table where you sort all the words in the dictionary and hash them into buckets with the key being the sorted version. So then dog and god end up in the same bucket. It gets better, because when you are input odg you find the bucket and return the entire bucket, its ALL the anagrams. Also, you only do the dictionary one time, then save it to a file so you can just load it already organized and ready to roll.

-> be sure to convert to all upper or all lower case

at this point you won't even loop. The whole thing collapses into
read the dictionary file
get input
return/print the result bucket

lots of problems are like this, where a file (or for smaller problems, a hard coded vector) with the 'answers' requires a throw-away program to generate but once you have the answers the rest of the program is trivial. Another example is factorials... a vector "fact" with the answers such that out = fact[in] gets rid of a loop to compute the values in favor of just having the answer in hand.

its notably more complicated if you need to do like text in, multiple words out (theater -> the,rate )
Last edited on
Topic archived. No new replies allowed.