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 itselfthat 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));