Aren't there multiple words that can be returned from the dictionary after various operations?
eg: input string: CODE If we go on walking the trie for the dictionary, we'll get results C, CO, COD, CODA, CODE. So multiple edit distance operations can be done to each of the instances shown above to give various results.. At which point shall we assume that ok, THIS is the word I want ? On Tue, Nov 15, 2011 at 12:44 AM, aniket chatterjee <[email protected]>wrote: > @Rajeev: The above algorithm assumes a source string and a destination > string. But here you are provided only the source string. And you will have > to edit it (minimally) such that the resulting string matches a word in the > dictionary. > > Need slight modification. Looking for the modification. (Interviewer told. > The same answer was given). > > > On Mon, Nov 14, 2011 at 4:59 AM, rajeev bharshetty > <[email protected]>wrote: > >> Levensteins algorithm >> >> On 14 Nov 2011 18:19, "aniket chatterjee" <[email protected]> wrote: >> > >> > yeah, that is normal bryteforce. Any better idea? >> > >> > On 11/14/11, Ankur Garg <[email protected]> wrote: >> > > We can use a trie here .. Create a trie with all words of dictionary . >> > > >> > > Now delete the last character of the word and check if such a word is >> a >> > > valid word . If not see if adding a new character can make it a valid >> word >> > > . If not delete the next character and repeat the process again . >> > > >> > > This is what I can think of here. Any other solutions/guesses ? >> > > >> > > >> > > >> > > On Mon, Nov 14, 2011 at 12:43 PM, Aniket <[email protected]> wrote: >> > > >> > >> You are given a word and a dictionary. Now propose an algorithm edit >> > >> the word (insert / delete characters) minimally to get a word that >> > >> also exists in the dictionary. Cost of insertion and deletion is >> same. >> > >> Write pseudocode for it. >> > >> >> > >> Seems like minimum edit distance problem but some modification is >> > >> needed. >> > >> >> > >> -- >> > >> You received this message because you are subscribed to the Google >> Groups >> > >> "Algorithm Geeks" group. >> > >> To post to this group, send email to [email protected]. >> > >> To unsubscribe from this group, send email to >> > >> [email protected]. >> > >> 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 [email protected]. >> > > To unsubscribe from this group, send email to >> > > [email protected]. >> > > 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 [email protected]. >> > To unsubscribe from this group, send email to >> [email protected]. >> > 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 [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Anup Ghatage -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
