Author |
Topic: Find a string inside a 2-dimensional array (Read 8947 times) |
|
Ved
Junior Member
Gender: 
Posts: 53
|
 |
Find a string inside a 2-dimensional array
« on: Jun 30th, 2012, 11:50pm » |
 Quote  Modify
|
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.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Find a string inside a 2-dimensional array
« Reply #1 on: Jul 1st, 2012, 1:11am » |
Quote Modify
|
Consider the matrix as a graph with neighbours connected, and then you can just do depth first search or something.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: Find a string inside a 2-dimensional array
« Reply #2 on: Sep 14th, 2012, 8:21pm » |
Quote Modify
|
on Jul 1st, 2012, 1:11am, 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 n2 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?
|
| « Last Edit: Sep 14th, 2012, 8:22pm by R » |
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
softsec
Newbie
Posts: 2
|
|
Re: Find a string inside a 2-dimensional array
« Reply #3 on: Jan 27th, 2013, 2:19am » |
Quote Modify
|
Is right?
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print