Backtracking – Search a Word In a Matrix

Objective : Given a 2D matrix of characters. Check whether the word exist in the matrix or not. If it exists then print its path. All movements are allowed (right, left, up, down and diagonally).

Example:

Search a Word In a Matrix

Search a Word In a Matrix

Approach:

We will show the path as increment counter

Search a Word In a Matrix - Solution

Search a Word In a Matrix – Solution

 

  • Create a solution matrix of the same structure as Matrix.
  • Try each cell a starting point.
  • Check current cell is not already used and character in it matches with the character in the word at index (starts will 0).
  • Check if index = length of the word, means we have found the word. return true and print the solution matrix.
  • If above criteria matches, mark that cell with a number Whenever any cell matches with the criteria, put a number corresponding to it in solution matrix. (start with 0 and keep incrementing it, it will show us the path for the word).
    • Now try to solve rest of the problem recursively by making index +1. Check all 8 directions ( up, down, left right, diagonally up-left, diagonally up-right, diagonally down-left, diagonally down-right). Check the boundary conditions as well
    • If none of the 8 recursive calls return true, BACKTRACK and undo the changes ( put 0 to corresponding cell in solution matrix) and return false.
  • Choose different starting point.
  • If all the starting points tried and solution not found, return false
  • See the code for better understanding.

Code:

Output:

 0 0 0 0 0
 0 1 0 5 0
 0 0 2 4 6
 0 0 0 3 7
 0 0 0 0 0

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

You may also like...

%d bloggers like this: