Given a list of words, find all possible words generated from the word in a performant way

Question

The way I am thinking of this is, say you have the word "palindrome". From that word, and given the dictionary of possible words which I have learned ("my dictionary"), you can generate:

do
in
drone
mind
plan
line
role
lad
pad
drape
...

Now imagine we do this programmatically, given a dictionary in computer form (a list of words in a text file). The question is how to somewhat efficiently find the words that can be generated from a word, for each word. So for every word in the dictionary, we find every word that can be generated from it.

The rules for generating the words from a given word are that you can only use each letter once, but you can pick which letter you want in any order.

The naive way I am starting to try to solve this problem is by first loading all words into a hashtable, an object in JavaScript. Seems like maybe putting them into a trie would be better, but not sure. Then iterate through each word in the hashtable. Try generating all possible combinations of letters of all possible lengths for the given word. I have no idea how to mathematically calculate how many combinations this is, but it seems like a lot. So for "palindrome" that is 10 letters, but seems like a ton of combinations just for 10 letter combinations, not to mention 9, 8, 7, 6....

So wondering how you might go about this more efficiently. I'm sure someone has already found the trick to solve this nicely.

Note, this is not a homework or interview question, I am just curious how to do this efficiently.

Answer 1

This might be a nice application of a trie data structure. This allows you to start looking through permutations of the word, while exiting early if there's no chance that word will be in your dictionary. For example, there's a lot of permutations of palindrome that start dp, but you won't consider any of them because dp is a dead end in the trie.

As you are looking through palindrome you might be looking at mode. You'll add that to the list of found words. There are further children in the trie for mode, but none for modep, modei, etc. you you can cut off those entire branches in your search. You will just continue on branch that have children leading on to words like model, modern.

It's fairly easy to turn a list of words into a trie using a dictionary in python:

trie = {}

with open('words.txt') as words:
    for word in map(lambda w: w.strip(), words):
        cur = trie
        for l in word:
            cur  = cur.setdefault(l, {})
        cur['word'] = True # defined if this node indicates a complete word

With a reasonable wordlist the root dictionary will probably have a key for every letter in the alphabet. But it quickly gets smaller as you descend. For example with a small word list looking up trie['w'] will have keys like ['a', 'e', 'h', 'i', 'o', 'r'] representing words in your dictionary starting with wa, we, ...etc. trie['q'] might just have one key u unless you have a dictionary with less common words.

Once you've built your trie, you can iteratively go thought the permutations of the word in question, adding words as you find them. This will go considerable faster than looking at all permutation because you exit the branch early when there's not more letters that match keys in the current branch of the trie.

Given the trie built above and a wordlist of 3000 common words, this quickly finds 100 words by recursively crawling the trie. Counting the number of times the inner for loop runs shows 2670 with a 3000 word dictionary -- not too bad considering there are 3.6 million permutations of the letters in the 'palindrome'. Using the much larger wordlist in /usr/share/dict/words which has roughly 250,000 words required 21543 loops. Looking up 'quilt' only ran 100 times with the large list.

Here's some Python code for traversing the trie for each valid permutation.

def findWords(word, trie = trie, cur = '', words = []):
    for i, letter in enumerate(word):
        if letter in trie:
            if 'word' in trie[letter]:
                words.append(cur + letter)
            findWords(word[:i] + word[i+1:], trie[letter], cur+letter, words )

    return words
words = findWords("palindrome")

Result:

['palm',
 'pale',
 'pain',
 'pair',
 'pan',
 'panel',
 'plan',

  ...

 'media',
 'ear',
 'earn',
 'end',
 'era']

Answer 2

Wouldn’t it be simpler to do it the other way round? Just look thru all words in the dictionary to see if that word can be generated from the target word. That way, all we have to do is subtract letters one by one, and as soon as a letter proves to be missing we can declare failure and go on to the next word. If we start by transforming the target word into a bag (counted set), our examination will go pretty fast.

Here's a Swift example. I'll need a couple of utility functions:

func wordToCountedSet(_ s:String) -> NSCountedSet {
    return NSCountedSet(array: Array(s))
}
func canMake(_ s:String, from cs:NSCountedSet) -> Bool {
    let cs = cs.copy() as! NSCountedSet
    for letter in s {
        if !cs.contains(letter) {
            return false
        }
        cs.remove(letter)
    }
    return true
}

Consider the efficiency of NSCountedSet (there's your hash) and the fact that canMake fails early and often.

To illustrate, imagine our dictionary consists of just "drone", "plan", "planet", and "xylophone". I won't bother looping through the dictionary; I'll just show that we get the right answer:

let cs = wordToCountedSet("palindrome")
canMake("drone", from:cs) // true
canMake("plan", from:cs) // true
canMake("planet", from:cs) // false
canMake("xylophone", from:cs) // false

With "planet" we don't fail until we get to the final "t", but with "xylophone" we fail on the first letter. The others have to subtract every letter of the tested word in order to succeed, but there's no simple way around that; even so, the longest it can take to succeed is the number of letters in the dictionary word. And it's all very quick because NSCountedSet is hashed. Obviously we could add some shortcuts (you can’t make a word longer than the original word, for example) but that’s not really the point.