the idea is always keep one distance word as next node so your tree will be something like this
dict : rat cat bat fat mat tat eat oat ......... bal given ekt ans eat : 1 down given pats bats aats cats.....pts ats pas pat pat----> bat : ans 2 iteration now recur here and check for ind 1 in same way until you find the answer now finding the answer , backtrack Algo rough sketch: queue q; findDist(char* str) { if(! str) return null; bool found = false; q.enq(str); while(!q.empty()){ char* str1 = q.deq(); char** str3 = getOneEditWords(str1); int i = 0; while(str3 && str3[i] ){ map.put(str1, str[i]); if(!indict(str[i])) { i++; q.enq(str[i]); }else{ found = true; printBacktrack(map, str1); break; } } } if(!found) print "no word matches with dict"; return; } printBackTrack(hashMap<string, string> map, string key) { char* val = map.value(key); if(!val) return; printBackTrack(map, val); print "val"; } On Nov 26, 8:47 pm, tech coder <techcoderonw...@gmail.com> wrote: > @vikas will u please elaborate ur answer. > @atul yeah thats true, target will be the words from the dictionary but we > dont have a specific target, here it will be brute force if we check newly > form word with each of the word in dictionary. > > > > > > > > > > On Sat, Nov 26, 2011 at 9:15 PM, atul anand <atul.87fri...@gmail.com> wrote: > > @vikas : to do BFS ..first you have to create tree . so what basis will > > you create a tree ? a dictionary can contains thousandss of word , just by > > taking arbitrary word from the dictionary and creating tree .... i guess > > will take lot of time. > > > @tech coder : target will be the words from the dictionary . > > > On Sat, Nov 26, 2011 at 6:19 PM, vikas <vikas.rastogi2...@gmail.com>wrote: > > >> this is well known problem, use the BFS traversal / Backtracking > > >> On Nov 26, 3:54 pm, tech coder <techcoderonw...@gmail.com> wrote: > >> > i think edit distance algorithm can not be used here because in edit > >> > distance problem we have a target string and a source string. Here we > >> dont > >> > have any target word. > >> > I think trie can be used with some preprocessing. > > >> > On Thu, Nov 24, 2011 at 11:59 PM, atul anand <atul.87fri...@gmail.com > >> >wrote: > > >> > >http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees > > >> > > this would help. > > >> > > On Thu, Nov 24, 2011 at 9:49 PM, Vijay Meena <vijay...@gmail.com> > >> wrote: > > >> > >> Can you please elaborate... > > >> > >> On Thu, Nov 24, 2011 at 12:14 AM, atul anand < > >> atul.87fri...@gmail.com>wrote: > > >> > >>> yes levenshtein distance and BK tree can be used to solve this. > >> > >>> where edge weight between nodes is equal to levenshtein distance. > > >> > >>> On Wed, Nov 23, 2011 at 7:14 PM, abhishek kumar < > >> afs.abhis...@gmail.com>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. > > >> > >>>> -- > >> > >>>> Abhishek Kumar > >> > >>>> B.Tech(IT) Graduate > >> > >>>> Allahabad > >> > >>>> Contact no-+919663082731 > > >> > >>>> -- > >> > >>>> 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. > > >> > >> -- > >> > >> 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* > >> > *"The Coder"* > > >> > *"Life is a Game. The more u play, the more u win, the more u win , the > >> > more successfully u play"* > > >> -- > >> 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* > *"The Coder"* > > *"Life is a Game. The more u play, the more u win, the more u win , the > more successfully u play"* -- 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.