How Word Scramble Solvers Use the Same Algorithm as Spell Checkers

Given the scrambled letters "AELPP", find all valid English words. The answer includes "APPLE", "PALE", "LEAP", "PLEA", "APE", "LAP", "PAL", "PEA", and others. A human might find 5-10 of these through trial and error. An algorithm finds all of them in milliseconds.

The algorithmic approach is elegant and teaches a useful pattern: using sorted character signatures as lookup keys.

The anagram signature approach

The key insight: two words are anagrams of each other if and only if they have the same sorted characters. "LISTEN" and "SILENT" both sort to "EILNST". This means you can build an index of all English words keyed by their sorted character signature.

function getSignature(word) {
  return word.toLowerCase().split('').sort().join('');
}

// Build the index
const dictionary = loadDictionary(); // ~270,000 English words
const index = {};
for (const word of dictionary) {
  const sig = getSignature(word);
  if (!index[sig]) index[sig] = [];
  index[sig].push(word);
}

// Find anagrams of "LISTEN"
index[getSignature('LISTEN')];
// Returns: ['enlist', 'inlets', 'listen', 'silent', 'tinsel']

This is O(k log k) per word for building the index (where k is word length), and O(k log k) for each lookup. With a hash map, the lookup is effectively constant time after the initial sort.

Extending to partial matches (scramble solver)

A word scramble differs from anagram finding. Given letters "AELPP", you want all words that can be formed using any subset of those letters (not necessarily all of them).

The approach: generate all possible subsets of the input letters, compute their signature, and look up each signature in the index.

For 5 letters, there are 2^5 - 1 = 31 non-empty subsets. For 7 letters, 127 subsets. This is manageable. For longer inputs (like Scrabble racks with blank tiles), the number of subsets grows exponentially and you need a more efficient approach.

function findWords(letters) {
  const results = new Set();
  const chars = letters.toLowerCase().split('');

  // Generate all subsets via bitmask
  for (let mask = 1; mask < (1 << chars.length); mask++) {
    const subset = [];
    for (let i = 0; i < chars.length; i++) {
      if (mask & (1 << i)) subset.push(chars[i]);
    }
    const sig = subset.sort().join('');
    if (index[sig]) {
      for (const word of index[sig]) {
        results.add(word);
      }
    }
  }

  return [...results].sort((a, b) => b.length - a.length);
}

The trie alternative

For very large input sets or when you need to handle wildcards (blank tiles in Scrabble), a trie (prefix tree) is more efficient. Each node represents a character, and paths from root to node represent prefixes. You walk the trie, consuming available letters at each step, and collect words at nodes marked as complete words.

function findWithTrie(trie, available, node = trie.root, prefix = '') {
  const words = [];
  if (node.isWord) words.push(prefix);

  for (const char of new Set(available)) {
    if (node.children[char]) {
      const remaining = [...available];
      remaining.splice(remaining.indexOf(char), 1);
      words.push(...findWithTrie(
        trie, remaining, node.children[char], prefix + char
      ));
    }
  }

  return words;
}

The trie approach avoids generating all subsets and prunes the search space early -- if no words start with "ZQ", the search does not explore that branch.

Practical applications beyond games

The same algorithmic patterns power:

• Spell checkers. Finding the closest valid word to a misspelling uses similar dictionary lookup structures.
• Autocomplete. Trie-based prefix matching is the foundation of every autocomplete system.
• DNA sequence analysis. Finding all subsequences that match known patterns uses similar subset enumeration.
• Cryptogram solving. Identifying words from a cipher text where the letter mapping is unknown.

I built a word scramble solver at zovo.one/free-tools/word-scramble-solver that finds all valid English words from any set of letters. Enter your letters, get every possible word organized by length. It is handy for Scrabble, Words with Friends, crossword assistance, and any situation where you need to find words from a set of available letters.

I'm Michael Lip. I build free developer tools at zovo.one. 500+ tools, all private, all free.