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.
