2

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.

enter image description here

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
1

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.

0

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.