How will you write a program to find jumbled words ?
The shotgun approach is the first one anyone is bound to follow at first. i.e. For all permutations of the letters, find if there is a match in the dictionary of words. You might do some optimizations to ignore repetitions etc. But this is O(n^2) complexity solution.
I read an elegant way to solve this here. The trick is to notice that the real answer and the jumbled word look the same when they the letters are sorted.
(Let’s ignore the time to sort the words for now, which is O(n*log(n)) I believe for decent algorithms.)
Here is a python snippet to solve the jumble:
#!/bin/env python
def find_jumble(jumble, word_file='/usr/dict/words'):
sorted_jumble = sort_chars(jumble)
for dictword in open(word_file, 'r').xreadlines():
if sorted_jumble == sort_chars(dictword):
yield dictword
def sort_chars(word):
w = list(word.strip().lower())
w.sort()
return w
while(1):
inp = raw_input("Enter word: ")
if not inp: break
for ans in find_jumble(inp):
print "Answer = ", ans
