Re: [algogeeks] MS Question : find word in 2D array
@utsav u haven't initialized match anywhere so ur algo fails On Thu, Jun 7, 2012 at 2:50 AM, utsav sharma utsav.sharm...@gmail.comwrote: 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 atul.87fri...@gmail.comwrote: i did this question long time back well simple brute force check can be doneyou can keep one flag matrix of same size to avoid necessary recursion. On 6/6/12, Ashish Goel ashg...@gmail.com 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 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. -- 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 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, 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 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.
[algogeeks] MS Question : find word in 2D array
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 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.
Re: [algogeeks] MS Question : find word in 2D array
i did this question long time back well simple brute force check can be doneyou can keep one flag matrix of same size to avoid necessary recursion. On 6/6/12, Ashish Goel ashg...@gmail.com 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 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.
Re: [algogeeks] MS Question : find word in 2D array
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 atul.87fri...@gmail.com wrote: i did this question long time back well simple brute force check can be doneyou can keep one flag matrix of same size to avoid necessary recursion. On 6/6/12, Ashish Goel ashg...@gmail.com 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 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. -- 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 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.