#include <algorithm> // for sorting
#include <string>
#include <unordered_map> // for storing words/anagrams
#include <iostream>
#include <fstream>
#include <set>
// create a class that will hold all words
class dictionary_t
{
public:
// load a text file with one word per line
void load(const std::string& filename)
{
std::ifstream file{ filename };
std::string word;
while (file >> word)
{
add_anagram(word);
}
}
auto& find_anagrams(const std::string& word)
{
const auto key = get_key(word);
// intentionally allow an empty entry to be made if word has no anagrams yet
// for readability easier error handling (not for space/time efficiency)
auto& anagrams = m_anagrams[key];
return anagrams;
}
// show all anagrams for a word
void show_anagrams(const std::string& word)
{
std::cout << "anagrams for word '" << word << "' are : ";
auto anagrams = find_anagrams(word);
for (const auto& anagram : anagrams)
{
if (anagram != word)
{
std::cout << anagram << " ";
}
}
std::cout << "\n";
}
private:
// this function is key to the whole idea
// two words are anagrams if they sort their letters
// to the same order. e.g. beast and betas both sort (alphabetically) to abest
std::string get_key(const std::string& word)
{
std::string key{ word };
// all anagrams sort to the same order of characters.
std::sort(key.begin(), key.end());
return key;
}
void add_anagram(const std::string& word)
{
// find the vector of anagrams for this word
auto& anagrams = find_anagrams(word);
// then add word to it (I use a set so all words will be unique even
// if input file contains duplicates)
anagrams.insert(word);
}
std::unordered_map<std::string, std::set<std::string>> m_anagrams;
};
int main()
{
dictionary_t dictionary;
dictionary.load("words.txt");
dictionary.show_anagrams("beast");
dictionary.show_anagrams("tacos");
return 0;
}
abets
baste
betas
beast
beats
acres
cares
races
scare
alert
alter
later
angel
angle
glean
ascot
coats
coast
tacos
aster
rates
stare
taser
tears
baker
brake
break
bared
beard
bread
debar
begin
being
binge
below
bowel
elbow
bores
robes
sober
capes
paces
space
caret
cater
crate
trace
cider
cried
dicer
claps
clasp
scalp
cruel
lucre
ulcer
dater
rated
trade
tread
dates
sated
stead
deist
diets
edits
sited
tides
dowry
rowdy
wordy
drawer
redraw
reward
warder
warred
earns
nears
saner
snare
earth
hater
heart
emits
items
mites
smite
times
ester
reset
steer
terse
trees
ether
there
three
hares
hears
rheas
share
shear
heaps
phase
shape
heros
hoers
horse
shore
lapse
leaps
pales
peals
pleas
sepal
leapt
petal
plate
pleat
least
slate
stale
steal
tales
teals
limes
miles
slime
smile
liter
litre
relit
tiler
loops
polos
pools
sloop
spool
lopes
poles
slope
manes
manse
means
names
mates
meats
steam
tames
teams
merit
mitre
remit
timer
nails
slain
snail
noter
toner
tenor
notes
onset
stone
tones
paled
pedal
plead
panel
penal
plane
pares
parse
pears
reaps
spare
spear
parts
strap
traps
parse
spare
spear
paste
tapes
peats
septa
spate
pelts
slept
spelt
piers
pries
spire
pines
snipe
spine
pinto
piton
point
pores
poser
prose
ropes
spore
reins
resin
rinse
risen
siren
reset
steer
terse
trees
rites
tiers
tires
tries
saint
satin
stain
salve
slave
vales
veals
serve
sever
veers
verse
sinew
swine
wines
wisens
skate
stake
steak
takes
teaks
state
taste
teats
steer
reset
trees
weird
wired
wider