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 <[email protected]> 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 <[email protected]> wrote:
> > For the mentioned scenario, it seems to be the only feasible solution.
> >
> > On Sun, Sep 18, 2011 at 3:57 AM, bharatkumar bagana <
> >
> >
> >
> >
> >
> >
> >
> >
> >
> > [email protected]> 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 <[email protected]>
> 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 <[email protected]
> >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 [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.
> >
> > >> --
> > >> 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 [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.
> >
> > > --
> >
> > > **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*
> > > <[email protected]>
> >
> > > --
> > > 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.
> >
> > --
> > 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 [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.
