for(i = 0; i < n; i++) for(j = 0; j < n; j++){ setColor(i, j) = black; if(A[i][j] == str[0]){ setColor(i, j) = blue; a = findWord(A, i, j, str, 1) if(!a) setColor(i, j) = black; else break; } }
findWord(A, i, j, str, k){ if(k == strlen(str)) return true; if(A[i-1][j-1] == str[k] && getColor(i-1, j-1) != blue) setColor(i-1, j-1) = blue; a = findWord(A, i-1, j-1, str, k+1); if(A[i-1][j] == str[k] && getColor(i-1, j) != blue) setColor(i-1, j) = blue; a = findWord(A, i-1, j, str, k+1); if(A[i-1][j+1] == str[k] && getColor(i-1, j+1) != blue) setColor(i-1, j+1) = blue; a = findWord(A, i-1, j+1, str, k+1); if(A[i][j-1] == str[k] && getColor(i, j-1) != blue) setColor(i, j-1) = blue; a = findWord(A, i, j-1, str, k+1); if(A[i][j+1] == str[k] && getColor(i, j+1) != blue) setColor(i, j+1) = blue; a = findWord(A, i, j+1, str, k+1); if(A[i+1][j-1] == str[k] && getColor(i+1, j-1) != blue) setColor(i+1, j-1) = blue; a = findWord(A, i+1, j-1, str, k+1); if(A[i+1][j] == str[k] && getColor(i+1, j) != blue) setColor(i+1, j) = blue; a = findWord(A, i+1, j, str, k+1); if(A[i+1][j+1] == str[k] && getColor(i+1, j+1) != blue) setColor(i+1, j+1) = blue; a = findWord(A, i+1, j+1, str, k+1); if(!a) setColor(i, j) = black; return a; } This is a pseudo code. I haven't considered the boundary cases to make it understandable. On Mon, Sep 19, 2011 at 12:21 AM, vikas <vikas.rastogi2...@gmail.com> wrote: > hmm, nice questions, can we create an efficient DS to query the > strings ?? > > > tried using trie but memory prints are very large ( O(n^2) )? :-(( > > > > On Sep 18, 12:59 pm, Anup Ghatage <ghat...@gmail.com> wrote: > > For the mentioned scenario, it seems to be the only feasible solution. > > > > On Sun, Sep 18, 2011 at 3:57 AM, bharatkumar bagana < > > > > > > > > > > > > > > > > > > > > bagana.bharatku...@gmail.com> wrote: > > > @anup : the time complexity will be very high ... > O(n*M*M)...n=#characters > > > to be checked...M=size of the matrix ... > > > > > On Sat, Sep 17, 2011 at 8:30 AM, Anup Ghatage <ghat...@gmail.com> > wrote: > > > > >> As WgpShashank once pointed out. > > > > >> Search the whole matrix for the first character instances, for each > > >> instance, send the array, string and that char's position to a > function that > > >> will recursively check its direct neighbors for the next character. > > >> Exhaustively check like that for each starting characters appearance > till > > >> you find the string, if any. > > > > >> On Fri, Sep 16, 2011 at 11:55 PM, Ankur Garg <ankurga...@gmail.com > >wrote: > > > > >>> In a matrix of. characters, find an string. String can be in any way > (all > > >>> 8 neighbours to be considered) > > >>> like find Microsoft in below matrix. > > > > >>> A > > >>> C > > >>> P > > >>> *R > > >>> *C* > > >>> *X > > >>> *S > > >>> **O > > >>> *P > > >>> *C* > > >>> V > > >>> *O* > > >>> V > > >>> N > > >>> *I* > > >>> W > > >>> G > > >>> *F > > >>> **M > > >>> *N > > >>> Q > > >>> A > > >>> *T* > > >>> I > > >>> T > > > > >>> *Any Ideas How to Solve/Approach this problem ?* > > > > >>> -- > > >>> 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. > > > > >> -- > > >> 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 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. > > > > > -- > > > > > **Please do not print this e-mail until urgent requirement. Go Green!! > > > Save Papers <=> Save Trees > > > *BharatKumar Bagana* > > > **http://www.google.com/profiles/bagana.bharatkumar< > http://www.google.com/profiles/bagana.bharatkumar> > > > * > > > Mobile +91 8056127652* > > > <bagana.bharatku...@gmail.com> > > > > > -- > > > 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. > > > > -- > > 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 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.