The Brides of Dracula

1 comment on Hacker News

1. NeutraljjsApr 22, 2010

   You're on the right track with the recursive dictionary search.

   For the Sling Blade Runner problem, I would make a trie (http://en.wikipedia.org/wiki/Trie) out of hash tables, like this:

   trie = { 'dracula': {'': None, 'dead': {'and': {'loving': {'it': "Dracula: Dead and Loving It!"}}}}, 'the': {'brides': {'of': {'dracula': "The Brides of Dracula"}}}, # ... }

   Then, for each word in each movie title, walk the trie from the beginning until you run out of matches (no match), or run out of words (at least one match).

   Your anagram server is similar, but since they're not ordered like movie titles, you have to walk your scrambled word(s) and only generate permutations that have a matching trie path.

   It's also quite possible to do it for phrases, not just words.

   You can cheat a little by representing your anagram as a 26-key multiset containing the number of times each letter appears (in Python, use a dict; in C, use an array of 26 integers).

   For each letter that appears in your anagram multiset one or more times, make a copy of the original multiset, and recursively descend the Dictionary trie, removing each matching letter from a new copy of the multiset (they're tiny, so don't worry). For each complete word you find, add it to a list of result candidates, along with the multiset representing the remaining letters in the anagrammatic phrase.

   Repeat the process for each result candidate, growing your list into a tree. Stop when you run out of matches, or when you run out of letters in your multisets. (You can set a maximum number of leftover letters to accept, if you're having trouble matching a phrase).

   If you test the letters in alphabetical order, your result phrases will already be sorted.