Given a two dimensional matrix of alphabets, search the given word in all directions. Below is an example to search for the word "TEAM":
No of occurrences is 4 in matrix below.
What is the best approach to solve this?
Its not a dictionary word. Its simply sequence searching in all the directions.
2
I did something similar time ago. You should take advantage of the fact that words are a ordered set of characters. So, you perform a linear search over the matrix for the first letter, then you recursively call the directional search.
To simplify computational complexity you can add some constraint, eg, if word.length > number of characters on that direction don't start searching.
The recursive function signature would be like:
boolean search(string word, int direction)
with terminal case
if (word.length==1) return isNextLetterInDirection(word, direction);
and the search being
search(substring(word, 0, word.length-1), direction);
This algorithm also cover palindrome cases and words including their syllables.
You can use backtracking for solving this problem, proceed till you find the word completing else backtrack.
While proceed there is a constraint which to proceed in the same direction with which you started.
For example if you are going “UP” then from next character you should go “UP” Only.