# Find number of occurrence of a word in a 2D matrix of Characters

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.

• Your example does not cover corner cases where multiple occurences overlap (what about a palindromic "TEAMEAT" sequence in the matrix?). If multiple solutions exist, do you want to produce them all or only one? – coredump May 11 '14 at 7:25
• all of them..above is just example. no palindromic sequence only that word. – Arvind May 11 '14 at 13:24

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.