Jumble Word Algorithm

Question

Given the word jumble (i.e. ofbaor), what would be the approach to deciphering the letters to create a real word (i.e. foobar)? I could see that this has several approaches, and I think I know how I will do it in .NET, but I'm curious to see what other solutions look like (always happy to see if my solution is optimal or not).

This is not homework or something like that, I just noticed that a word appeared in the local comics section of the newspaper (yes, a good newfangled news feed), and the engineer began to think in me.

edit: please write some pseudo-code or real code if you can; it is always a pleasure to try and expand your knowledge of the language by seeing such examples.

Answer 1

You have a dictionary that is entered by the letter of each word in sorted order. Then take a sort of letters - find all the words in the dictionary by this line of sorted letters.

So, as an example, the words “bear” and “naked” will be in the dictionary as follows:

key word ----- ------ aber bear aber bare 

And if you are given a mess, “earb”, you sort the letters “aber” and you can search for both words in the dictionary.

Answer 2

Create all line permutations and find them in the dictionary.

You can optimize the search for shorter lines that begin words, and if the dictionary does not have words of suitable length that begin with these lines, excluding permutations starting from these letters from further consideration.

Answer 3

There are several articles in CodeProject here and here . The second uses recursion. Wikipedia also describes a couple of algorithms here . The Wikipedia article also mentions a program called Jumbo, which uses a more heuristic approach that solves the problem as a person. There seem to be several approaches to the problem.

Answer 4

Depending on the length of the string, the WhirlWind approach may be faster, but an alternative way to do this, which is more or less O (n) complexity, instead of creating all the permutations of the string and looking for them, you go through all the words in the dictionary and see can they be built from the input string.

A really smart algorithm that knows in advance the number of words in a dictionary can do something like this:

 sort letters in jumbled string if factorial(length of jumbled string) > count of words in dictionary: for each word in dictionary: sort letters in dictionary word if sorted letters in dictionary word == sorted letters in jumbled string: append original dictionary word to acceptable word list else: create permutation list of jumbled letters for each permutation of letters: search in dictionary for permutation if permutation in dictionary: add word to acceptable word list 

Answer 5

http://www.codeproject.com/KB/game/Anagrams2.aspx