#include <algorithm>
#include <iostream>
#include <locale>
#include <map>
#include <vector>
#include <set>
// create a class to hold anagram information
class anagram_dictionary_t
{
public:
// create a dictionary based on an input list of words.
explicit anagram_dictionary_t(const std::initializer_list<std::string>& words)
{
for (std::string word : words)
{
auto key = make_key(word);
std::string lower{ word };
to_lower(lower);
m_anagrams.insert({ key, lower});
}
}
// find all the words that match the anagram
auto find_words(const std::string& anagram)
{
// get the unique key for input word
// this is done by sorting all the characters in the input word alphabetically
auto key = make_key(anagram);
// lookup all the words with the same key in the dictionary
auto range = m_anagrams.equal_range(key);
// create a set of found words
std::set<std::string> words;
for (auto it = range.first; it != range.second; ++it)
{
words.insert(it->second);
}
// return the words
return words;
}
// function to check if two words are an anagram
bool is_anagram(const std::string& anagram, const std::string& word)
{
auto words = find_words(anagram);
return (words.find(word) != words.end());
}
private:
// make a unique key out of an input word
// all anagrams should map to the same key value
static std::string make_key(const std::string& word)
{
std::string key{ word };
to_lower(key);
// two words are anagrams if they sort to the same key
std::sort(key.begin(), key.end());
return key;
}
static void to_lower(std::string& word)
{
for (char& c : word)
{
c = std::tolower(c, std::locale());
}
}
std::multimap<std::string, std::string> m_anagrams;
};
int main()
{
anagram_dictionary_t anagram_dictionary{ {"Apple", "Apricot", "Avocado", "Banana", "Bilberry", "Blackberry", "Blueberry" } };
std::string anagram{ "aaannb"};
auto words = anagram_dictionary.find_words(anagram);
std::cout << "input word = " << anagram << "\n found words : ";
for (const auto& word : words)
{
std::cout << word << "\n";
}
return 0;
}
