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 <[email protected]> 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 <[email protected]> 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 <[email protected]>wrote:
>
> >> this is well known problem, use the BFS traversal / Backtracking
>
> >> On Nov 26, 3:54 pm, tech coder <[email protected]> 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 <[email protected]
> >> >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 <[email protected]>
> >> wrote:
>
> >> > >> Can you please elaborate...
>
> >> > >> On Thu, Nov 24, 2011 at 12:14 AM, atul anand <
> >> [email protected]>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 <
> >> [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.
>
> >> > >>>> --
> >> > >>>> 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 [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.
>
> >> > --
> >> > *
>
> >> > 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 [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.
>
> --
> *
>
> 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 [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.
