wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> microsoft >> Find a string inside a 2-dimensional array
        
(Message started by: Ved on Jun 30^th, 2012, 11:50pm)

Title: Find a string inside a 2-dimensional array
Post by Ved on Jun 30^th, 2012, 11:50pm

In a matrix of characters, find an string. String can be in any way (all 8 neighbors 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

String Microsoft is present in the matrix above ?
There also a slight variation where a diagonal neighbor is not considered.

Title: Re: Find a string inside a 2-dimensional array
Post by towr on Jul 1^st, 2012, 1:11am

Consider the matrix as a graph with neighbours connected, and then you can just do depth first search or something.

Title: Re: Find a string inside a 2-dimensional array
Post by R on Sep 14^th, 2012, 8:21pm

on 07/01/12 at 01:11:27, towr wrote:

Consider the matrix as a graph with neighbours connected, and then you can just do depth first search or something.

As the string can be hidden anywhere and in any shape (just like the one given in example), I agree that graph seems to be a good choice.

But representing the matrix and neighbors in Graph will be quite expensive. There will be n² nodes. Next adding edges to Adjacency matrix/list will be again expensive.

Now once the graph is ready and we start the DFS,
1. From which node do we start the DFS?
2. In DFS each node is visited max twice, so while looking for a string, if some node/character is already visited twice, we won't be able to find it again.

Right?

Title: Re: Find a string inside a 2-dimensional array
Post by softsec on Jan 27^th, 2013, 2:19am

Is right?