Algorithm Question On Finding All Valid Words In Dictionary

Question

Given a dictionary (just a list of strings).

You receive a feed of an unknown number of letters from an external source. Given the string of letters, how would you go about listing all valid words (from the diciontary) you can make from any combination from those letters.

So if you receive: abpplead

You should find apple, bad, pad, lead, etc.

I know there's no best answer. But what are some reasonably efficient ways to do it, what data structures to use, etc.

Also, assume you can pre-process the input, so you can choose to store the input letters as they come in in whatever data structure you want.

Answer 1

for each word in dictionary check if it's from letters you have only.
To check this you may create helper struct like dict x[letter: amount], initialize it with amounts of given letters and then:

for each word 'w' in dictionary
    init x from given letters

    for each letter `ch` in word `w` 
        --x[ch]
        if x[ch] < 0
            break, do not add w to result

    result.add(w)

Answer 2

If you're not allowed to perform any pre-processing on that list of strings, then there's no "reasonably efficient solution": you're going to have to iterate all over the list, checking for each word whether it can be composed as required (i.e., its signature, see below, is uniformly less than the incoming bunch's signature). O(N) for N strings in the list.

If preprocessing is allowed (you preprocess the list once and then answer several queries, enough to amortize the preprocessing costs), then for each word in the list make a "signature", which is the array of 26 integers counting the occurrences of each letter in the string (assuming it's English and case-insensitive -- extensions are obvious). As you go, build a map from each signature to the list of words that have that signature. This preprocessing is roughly O(N) for a HashMap.

Now, given a bunch of K letters, you can compute the bunch's signature and look up each list of words with that signature in the map; repeat for all uniformly-less signatures (O(2^K) is an upper bound here). So for Z such lookups you pay O(N + Z * 2^K) (vs O(Z * N) without preprocessing), so you gain (for large enough numbers so that O() estimates make sense) if N > 2^K.

Answer 3

1.Create a tree structure for each word in the dictionary. The tree branches on each letter, e.g. first level of the tree are the letters a-z, next level is again a-z IF there are any words using that combination, etc. The leaves of the tree are the words.

Then, when you get the letter combination, just start with all choices for the first letter, travel the tree down that branch, and then make a search for all choices for the second letter, etc.

Although this may seem expoential, because not all combinatoins are possible, you will find that invalid branches are quickly pruned.

Answer 4

Use a rete algorithm and treat the problem as a problem in rule-based domain. Words are rules (with their own letters as rule patterns). For each set of letters given, you apply the rule-base and all the words that match will 'fire'. Rinse and repeat. :)

[Edit p.s.]

The motivation here is this: "Rete performance is theoretically independent of the number of rules [words in dictionary in your case] in the system".

Answer 5

Put the dictionary into a trie. Then put the letters into an counter array indexed by their character values, maintaining the counts for each letter (let call this counts[]). Then traverse the trie in depth first search order, decrementing the counts[letter] value for each letter while traversing downward, and incrementing it on the way back up. Now, any time a counts[letter] is about to go negative, stop and traverse back upwards. Any time you reach a word terminator, output the result.

Answer 6

preprocess the dictionary into a dawg, and then use one of the dawg-walking algorithms to search for substrings. i have some basic ruby code for working with a dawg here; it proved too slow in practice so i moved over to ocaml (unreleased), but it should give you an idea of how to find anagrams. for subanagrams, just add an extra check for a word ending even if your bag is not empty.