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 down to the leaves. Now output the one with the least edit distance as the correct spelling. You might want to keep a bound on the max edit distance and say no suggestions if edit distance exceeds that.
On Tue, May 3, 2011 at 9:47 AM, Sathaiah Dontula <don.sat...@gmail.com>wrote: > is it not EDIT DISTANCE (DP) problem ? > > Thanks & regards, > Sathaiah Dontula > > > On Tue, May 3, 2011 at 9:03 AM, lichenga2404 <lichenga2...@gmail.com>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 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 spelling suggestion, or >> "NO SUGGESTION" if no suggestion can be found. The program should >> print ">" as a prompt before reading each word, and should loop until >> killed. >> >> Your solution should be faster than O(n) >> >> For example: >> >> > sheeeeep >> sheep >> > peepple >> people >> > sheeple >> NO SUGGESTION >> The class of spelling mistakes to be corrected is as follows: >> >> Case (upper/lower) errors: "inSIDE" => "inside" >> Repeated letters: "jjoobbb" => "job" >> Incorrect vowels: "weke" => "wake" >> Any combination of the above types of error in a single word should be >> corrected (e.g. "CUNsperrICY" => "conspiracy"). >> >> If there are many possible corrections of an input word, your program >> can choose one in any way you like. It just has to be an English word >> that is a spelling correction of the input by the above rules. >> >> Final step: Write a second program that *generates* words with >> spelling mistakes of the above form, starting with correctly spelled >> English words. Pipe its output into the first program and verify that >> there are no occurrences of "NO SUGGESTION" in the output >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- regards, chinna. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
