@utsav u haven't initialized match anywhere so ur algo fails
On Thu, Jun 7, 2012 at 2:50 AM, utsav sharma <[email protected]>wrote: > i think it can be solved using DP > word="bcdf" take hash of word h[b]=1 h[c]=2 h[d]=3 h[f]=4 > given 2d matrix m[][]= > {b c b e f g h > b c d f p o u > d f d f g k p } > > take another matrix match[][] > if( h[ m[i][j] ] > 0 ) //if this char is in word then > {a=h[ m[i][j] ]; > if (match[i-1][j] ==a-1 || match[][]=a-1 || match[][]=a-1 ) check > prev element of row / diagonal /column > match[i][j]=a; > } > else if char is not matched, then match[i][j] will contain longest prefix > match(as in KMP). > if at any instance we get match[i][j]==no. of chars in word then we will > backtrack it to get the string. > correct me if i'm wrong !! > > On Wed, Jun 6, 2012 at 10:39 PM, atul anand <[email protected]>wrote: > >> i did this question long time back.... >> well simple brute force check can be done....you can keep one flag >> matrix of same size to avoid necessary recursion. >> >> >> On 6/6/12, Ashish Goel <[email protected]> wrote: >> > WAP to find a word in a 2D array. The word can be formed on >> > row/col/diagnal/reverse diagnal >> > >> > Best Regards >> > Ashish Goel >> > "Think positive and find fuel in failure" >> > +919985813081 >> > +919966006652 >> > >> > -- >> > 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. >> >> > > > -- > Utsav Sharma, > NIT Allahabad > > -- > 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, Bhaskar Kushwaha Student CSE Third year M.N.N.I.T. Allahabad -- 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.
