@piyush: what is time and space complexity of u'r sol..
On Mon, Sep 19, 2011 at 11:03 AM, Piyush Grover
<piyush4u.iit...@gmail.com>wrote:
> sry, in the findWord function all a's are different e.g
> a0, a1....a7
>
> and if(!a) is actually if(a0||a1||...||a7)
>
> thnx
> piyush
>
>
> On Mon, Sep 19, 2011 at 1:10 AM, Piyush Grover
> <piyush4u.iit...@gmail.com>wrote:
>
>> 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.
>
--
**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.
