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 neighbouring. 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.

This problem can be solved with the help of backtracking.

We shall call “adjacentSearch” function recursively to check the given word is present or not.

Take an example to search the word “ABF” from the given input array.

First we shall see “A” is present by using “adjacentSearch”, if it is present then we shall call again “adjacentSearch” to search for “B”. To search “B”, “A” is having only 1 way, i.e. to the right. And we find the element “B” by calling “adjacentSearch” recursively. Then for “B” it is having 3 ways, either to go towards one step right or to one step down or one step left. If we go down, we find “F” thus the result.

Below is the code to achieve this:

bool searchFurther =

adjacentSearch(board, word, i+1, j, index+1) || // up
adjacentSearch(board, word, i-1, j, index+1) || // down
adjacentSearch(board, word, i, j-1, index+1) || // left
adjacentSearch(board, word, i, j+1, index+1); // right

“searchFurther” will tell the “adjacentSearch” to search further or not.

According to the question, a letter has to be used only once.

For example “ABA”. First we find element “A” by calling “adjacentSearch”. Then A is already been used. Then we search “B”, and we find it. Then again we search for “A”. “B” has 3 ways to find the result, one step towards left, one step towards right, one step towards down.

Since we have already used “A”, we cannot consider it. Hence to check that by replacing the already searched element by “*” as shown below:

board[i][j] = ‘*’;

and replace it back with the original element once we are done with recursive search.

Solution in C++

/*
* File     : word_search.cpp
*/
#include<iostream>
#include<vector>

using namespace std;
 

bool adjacentSearch(vector<vector<char>>& board, const string& word, int i, int j, int index)
{
  if(index == word.size()) return true; 
        
  if(i < 0 || j < 0 || i > board.size()-1 || j > board[0].size()-1)
  {
      //boundry condition 
      return false;
  }

  if(board[i][j] != word[index])
  {
      return false; // do not match
  }
  
  // match! change the content, to avoid duplicated search
  board[i][j] = '*'; 

  bool searchFurther =  adjacentSearch(board, word, i+1, j, index+1) || // up
                        adjacentSearch(board, word, i-1, j, index+1) || // down
                        adjacentSearch(board, word, i, j-1, index+1) || // left
                        adjacentSearch(board, word, i, j+1, index+1);   // right
       board[i][j] = word[index]; // modify it back!
       return searchFurther;
}


bool exist(vector<vector<char>>& board, string word) 
{

  //Iterate through all the elements as starting character
  for(int i = 0; i < board.size(); ++i)
  {
    for(int j = 0; j < board[0].size(); ++j)
    {
      if(adjacentSearch(board, word, i, j, 0))
        return true;
    }
  }
  return false;

}

int main()
{
  vector<vector<char> > input = { { 'A','B','C','E'},
                                  { 'S','F','C','S' },
                                  { 'A','D','E','E'},
                                };

    //string word = "ABA";
    string word = "ABCCED";

if(exist (input, word))
  cout<<"The word is present"<<endl;
else
  cout<<"Word is not present"<<endl;



return 0;
}

Output:

The word is present