An Simple Algorithm Can be use Matrix or Graph (BFS Will Work) , We Need to
Visualize the problem :)
This Problem is similar to finding neighbor & solution that i posted the
matrix-local maxima problem
Problem Solving Apparoach
we start matching from the first element; if it matched we matched the 2nd
element in the neighbors (8) of first match; do this process recursively;
when last character of input pattern matches, return true.
we also need another 2-d array to make cell visited or not as true.
If your pattern matching fails at some place, you start matching from the
beginning (of pattern) in remaining cells. for this Also, we need the
current position of input matrix, from where we need to start. While
returning, you unmark visited cells.
An Efficient Algorithm:
Step1. Check Boundary Conditions cols > N or row > M etc. return false
Step2. if we come to last character e.g. whole pattern matched return true;
Step 3. if we got visited cell again return false.
Step 4. if the value at given cell is not equals to character at 1st ( 0th
index ) position in pattern/string then
call recursively either in same or same column.
Step 5. if character value matches with given cell the set this cell as used
true. & search for remaining sub- string of pattern in all neighbor of this
cell , for call recursively & return OR operation of all such recursive call
mark this cell unused while leaving.
Step if we done & didn't find pattern then return false.
correct me if i missed anything or better approach exist ?
*Thanks
Shashank Mani
Computer Science
Birla Institute of Technology Mesra*
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/sRPVkhNamdIJ.
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.
