Unscrambling Words

Problem Statement

Write a program that will take these scrambled words from scrambled.txt, and compare them against wordlist.txt to unscramble them, e.g., sleewa unscrambles to weasel.

Solution

Pre-process wordlist.txt into a dictionary keyed by the sorted version of the anagram, e.g., weasel is keyed under aeelsw. To support multiple anagrams, the value should be a list of all strings from wordlist that share the sorted anagram. Iterating through scrambled.txt becomes a lookup operation keyed on the sorted string.

Implementation: Building a Word List Index

#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>

#include "unscramble_words.h"

namespace unscramble_words {

void PrintTo(const UnscrambledPair& pair, std::ostream* os) {
    *os << "\nUnscrambledPair{scrambled=" << pair.scrambled_word
        << "; unscrambled=";
    for (const auto& word : pair.unscrambled_words)
        *os << word << ",";
    *os << "}";
}

std::vector<UnscrambledPair> unscramble(
        const std::vector<std::string>& scrambled, const std::vector<std::string>& word_list) {
    // Pre-process `word_list` into a lookup table keyed by sorted anagrams.
    std::unordered_map<std::string, std::vector<std::string>> word_list_index{};
    word_list_index.reserve(word_list.size());
    for (const auto& word : word_list) {
        std::string k = word;
        std::ranges::sort(k);
        word_list_index[k].push_back(word);
    }

    // Iterate through `scrambled` and locate pairs.
    std::vector<UnscrambledPair> pairs{};
    pairs.reserve(scrambled.size());
    for (const auto& word : scrambled) {
        std::string k = word;
        std::ranges::sort(k);

        const auto it = word_list_index.find(k);
        if (it == word_list_index.end())
            continue;

        pairs.emplace_back(UnscrambledPair{word, it->second});
    }
    return pairs;
}

}

Notes

operator[] is an inserting access, i.e., map[k].push_back(word) is equivalent to:

if (k not in map) {
    map[k] = empty vector;
}
map[k].push_back(word);

… which is fine for a write path for “create if missing”. However, if reading, map[k] creates a new entry in the map on what was supposed to be a read-only operation. Compare this to map.at(k), which throws std::out_of_range if k is not in map.

Avoid the double lookup from contains-then-fetch, e.g.,

if (!word_list_index.contains(k))
  continue;

pairs.emplace_back(UnscrambledPair{word, word_list_index[k]});

… by using std::map<Key,T,Compare,Allocator>::find, e.g.,

const auto it = word_list_index.find(k);
if (it == word_list_index.end())
  continue;

pairs.emplace_back(UnscrambledPair{word, it->second});

References

[2/11/2012] challenge #3 [difficult] : r/dailyprogrammer. www.reddit.com . Accessed May 3, 2020.
std::map<Key,T,Compare,Allocator>::operator[] - cppreference.com. en.cppreference.com . Accessed Jul 2, 2026.
std::map<Key,T,Compare,Allocator>::at - cppreference.com. en.cppreference.com . Accessed Jul 2, 2026.