LeetCode : Word Search

Word Search : Given a 2D board and a word, search 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 =
[
[‘Q’, ‘U’, ‘I’, ‘J’],
[‘O’, ‘F’, ‘C’, ‘E’],
[‘X’, ‘U’, ‘K’, ‘M’] ]

Given word = “QUICK”, return true.
Given word = “ICE”, return true.
Given word = “QUFM”, return false.
Backtracking Algorithm :
First traverse the given board and find x,y location such that grid[x][y] == word[0].
So that we can make a recursive call from the present coordinate in our pair of vectors.

Create a visited array of the same size of given board,
which will help us to keep track of visited coordinate so that we won’t make a recursive call again on the already used coordinate.

If a present coordinate leads us to the solution then
increment the length variable and check for another possible move in all four directions.

If any one of the four directions leads us to the solution ,
again make a recursive call from that coordinate.

If none of the 4 coordinate lead us to the solution,
backtrack by marking current coordinate vis[x][y] = false and also decrement length variable.

So that it can be used again, if a recursive call from another coordinate comes.

Repeat for whole matrix.

class Solution {
    public boolean exist(char[][] board, String word) {
	
	// first we need to find the starting position so we try all the index(row,column) as the potential starting point
        for (int i =0;i<board.length;i++)
        {
            for (int j =0;j<board[i].length;j++)
            {
	   // if yes then no need to do further calculation 
                if (checkExist(board,word,i,j,0))
                    return true;
            }
        }
        return false; // if all the positions are checked and no potential candidate(word not found) the return false;
    }
    
    public boolean isPossible(char [][] board,String word,int i,int j,int x){
      if (i>=board.length||i<0||j<0||j>=board[0].length 
           ||  x>=word.length() || word.charAt(x)!=board[i][j]
           || board[i][j]=='0')
              return false;
      // You can also segregate boundary, visibility condition etc.
return true;
    }	
    public boolean checkExist(char [][] board,String word,int i,int j,int x)
    {
          if(!isPossible (board,word,i,j,x) ) return false;   
	   
	// if we found the last character then return true;
        if (x==word.length()-1&&word.charAt(x)==board[i][j])
            return true;
        
	/* store the current character in a temporary variable 
	 this is done so that we can maintain which position is visited or not
	 here this character will be set to '0' and later after processing
         from this index it will be again restored it also faciliates 
         less memory as we are not creating any other 2-d array 
         to mark those indexes which are visited. */
        
        char temp = board[i][j];
        board[i][j]='0';

        x++; // increment the count of length or index of word by one.
        int iA = { 0, -1, 1, 0 };
        int jA = { 1, 0, 0, -1 };
        boolean b = false;
        for(int ia = 0; ia < iA.length; ia++ ){
            for(int ja = 0; ja < jA.length ; ja++) {
               b = b || checkExist(board, word, i+iA[ia], j+jA[ja],x)
            }
        }
  
        
	// restore the original value and return .
        board[i][j]=temp;
        return b;
    }
}

Find more LeetCode Questions
Time Complexity Analysis :-

From a particular position we can go into 4 other positions.
Let F(n) denotes the processing done by the function checkExist();

essentially this function is calling itself 4 times (for 4 directions)

question is how many times it will call itself
that will be K(length of word) as then word will already been found.
	T(n) = F(n)
	     = 4*F(n-1)...
		 = 4*4*F(n-2)...
		 = 4*4*4*4... (K times as K is the length of the word)
	
Total time complexity = M*N*(Pow(4,k));


	
Similar Articles