Solve word search using backtracking

In this post we are gonna learn how to apply backtracking to solve word search problem

Problem Statement :

Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring.

The same letter cell may not be used more than once.

Example: board =[ [‘A’,’B’,’C’,’E’], [‘S’,’F’,’C’,’S’], [‘A’,’D’,’E’,’E’]]

Given word = “ABCCED”, return true.

Given word = “SEE”, return true.

Given word = “ABCB”, return false.

Step by step solution to the problem :

First thing which comes to our mind after seeing this problem is that let’s generate all the possible permutations using the board and rule defined, then check if input word matches any one of those.This brute force approach will work but not efficient.

As we know in Backtracking, we don’t generate all possible solutions, rather than we keep go on checking whether the solution is correct or not at every step. If it is correct, we continue generating subsequent solutions to the problem. If it is incorrect we backtrack to the previous step and check for the other solutions. This prevents in generating invalid recursion subtrees and saves a lot of time.

So we will try to apply backtracking in this problem but how?

To search a given word we can start with any character in the board and try to apply the rule given in the problem for matching characters input word starting from first index, if we can match all characters input word using backtracking then voila we found a solution, else we start with next character in the board try applying same logic. If we don’t find a match even after trying with all the characters in the board as starting character for the input word, then we can conclude that it’s not possible to construct input word from board. Below is the code for the same :

public boolean exist(char[][] board, String word) {
   if(board==null || board.length==0 || board[0].length==0)
   return false;        
   for(int i=0;i<board.length;i++){       
     for(int j=0;j<board[0].length;j++){ 
        if(backtrack(board,word,0,i,j)) return true;  
     }       
   }       
  return false;  
}

Base Case:

If there is no character in the board then it’s not possible to construct any word using the board.

if(board==null || board.length==0 || board[0].length==0)
   return false;

Backtracking Logic :

Lets discuss the backtrack function in detail

boolean backtrack(char[][] board,String word,int index,int i,int j){        
 if(board[i][j]!=word.charAt(index)) return false;
 if(index==word.length()-1) return true;   
 char c=board[i][j];  
 board[i][j]=' ';    
 boolean exist=false;    
 if(i>0){ 
   exist|=backtrack(board,word,index+1,i-1,j); 
   if(exist) return exist;    
 }         
if(j>0){           
  exist|=backtrack(board,word,index+1,i,j-1); 
  if(exist) return exist;   
 }      
if(i<board.length-1){
  exist|=backtrack(board,word,index+1,i+1,j);       
  if(exist) return exist;       
 }        
if(j<board[0].length-1){   
  exist|=backtrack(board,word,index+1,i,j+1);    
  if(exist) return exist;     
 }          
 board[i][j] =c;     
 return exist;  
}

The logic for this goes as below

1. First we check if the current char of word doesn’t match with board[i][j] then return false, else we mark board[i][j] as visited in current iteration by doing board[i][j]=’ ‘;
2. Then we call backtrack with valid left, right, top and down of the current board position with next character of the word.If any one of the path taken in this step matches the whole word we return true. To check if it matches the whole word or not we check that have we reached up-to last index of word by checking index==word.length()-1
3. Eventually after every step if we are unable to match the word, we restore the current character by doing board[i][j] =c; and move to explore other dimensions hoping that will leads to positive solution.

The complete code for this problem can be found in https://github.com/GyanTech877/algorithms/blob/master/dynamicprogramming/EditDistance.java.

Happy Learning 😎