You may have to use a trie and also the edit distance for this problem.
Firstly , walk down the trie as you can keep matching the alphabets.
When you encounter a first mismatch , findout the edit distance for the rest
of the substring of the input with all of the strings possible from that
node do
is it not EDIT DISTANCE (DP) problem ?
Thanks & regards,
Sathaiah Dontula
On Tue, May 3, 2011 at 9:03 AM, lichenga2404 wrote:
> The question in an interview. And I got lost with this one.
>
> Could you guys give some algorithm or idea on this ?
>
>
> Write a program that reads a large list of
I have got a solution for this problem but It is greater than O(n^2).
The idea is to take the edit distance with selected words from dictionary of
all words in english and output the word with min edit distance (An edit
distance is number of insertions, deletions and replacement operations
needed
The question in an interview. And I got lost with this one.
Could you guys give some algorithm or idea on this ?
Write a program that reads a large list of English words (e.g. from /
usr/share/dict/words on a unix system) into memory, and then reads
words from stdin, and prints either the best
