Introduction
In this blog, we will be acing the problem word search so let’s understand the problem statement clearly first. The problem goes like this: You are given an M * N grid named ‘board’, and you are also given a string named ‘word’. Now you have to find out whether the given string can be constructed from the sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same cell of a grid cannot be used twice.

Also see, Data Structures
Let’s understand this with the help of an example:
You are given a 2-D grid named ‘board’ like this:
A |
B |
C |
E |
S |
F |
C |
S |
A |
D |
E |
E |
Let you be given a string, ‘word’ as “ABCCED". Now you have to return true or false based upon whether that string can be constructed inside the grid or not. Let’s try to form the string inside this grid:-
A |
B |
C |
E |
S |
F |
C |
S |
A |
D |
E |
E |
Now you can see that boxes colored in green show that this 2-D grid can accommodate the string. So the output that you have to print is true.
Okay so now you have understood the problem statement of word search clearly. Let’s move toward its solution:
Recommended: Do try the Problem yourself before moving on to the solution.
Recommended topic, kth largest element in an array, and Euclid GCD Algorithm
Approach to the Problem
First, we have to check whether the first word of our string that is the ‘word[0]’ is present in the grid or not. Now there can be three cases:
- ‘word[0]’ is not there in the grid. So in this case simply, your output should be false because if the grid is not containing the first character of our string then what’s the point of finding the rest of the string. Right?
- ‘word[0]’ is present only once in the grid. So, in this case, we try finding the rest of the string and if the rest of the string is present then the output would be true otherwise, the output will be false.
- ‘word[0]’ is present more than once in the grid. Now, this is the super important point to pay attention to. Most students fail to analyze this case. Here what you need to do is that you will call your function to find the rest of the string for the first occurrence of ‘word[0]’.If it returns true then great just print true as final output and you are done, but if it returns false then call the function again for the next occurrence of ‘word[0]’ and keep doing like this until you visit all occurrence of ‘word[0]’ in the grid.
Since we have found the first character of our string. Now let’s talk about the function which will be identifying the rest of the string in this 2-D grid.
Here it is mentioned that we can travel only in four directions in the grid that too horizontally and vertically. Now we will make calls in four directions adjacent to our current cell and if any one of them returns true then our output will be true otherwise our output will be false.
Now one more thing to discuss is that it is mentioned in the question that you cannot visit a cell twice. So in order to make sure that we visit one cell only once we will be changing the value of that current cell before making calls. Don’t forget to place the value back in the grid once your calls are over!
We have discussed the approach to this problem word search clearly. Now please try to code it on your own only then you will be able to learn to code.
Okay, so you tried coding it out on your own? Great! Let’s see how we have written code for this problem:-
Implementation in C++
#include <bits/stdc++.h>
using namespace std;
bool searchWord(vector < vector < char >> & board, string word, int startX, int startY, int n, int m) {
// If the string given to search is empty
if (word.size() == 0) {
return true;
}
// If the call is made to the cell beyond the boundary of the 2-D grid
if (startX < 0 || startX >= n || startY < 0 || startY >= m || board[startX][startY] != word[0]) {
return false;
}
// Storing the character placed at current cell in the board
char c = board[startX][startY];
// Replacing the character so that call cannot be made twice to a cell
board[startX][startY] = '*';
// Making calls in all four directions that are adjacent to the current cell
bool ans1 = searchWord(board, word.substr(1), startX, startY + 1, n, m);
bool ans2 = searchWord(board, word.substr(1), startX, startY - 1, n, m);
bool ans3 = searchWord(board, word.substr(1), startX + 1, startY, n, m);
bool ans4 = searchWord(board, word.substr(1), startX - 1, startY, n, m);
// Placing the character back in the board
board[startX][startY] = c;
// If answer of any of the four calls comes out to be true
if (ans1 || ans2 || ans3 || ans4) {
return true;
}
// If the answer of all four calls comes out to be false
else {
return false;
}
}
bool exist(vector < vector < char >> & board, string word) {
int n = board.size();
int m = board[0].size();
int i = 0;
int j = 0;
for (i = 0; i < n; i++) {
for (j = 0; j < m; j++) {
// Checking if grid contains the first character of the string
if (board[i][j] == word[0]) {
// Calling the function for rest of the string
bool ans = searchWord(board, word, i, j, n, m);
// If ans comes out to be true
if (ans == true) {
return true;
}
}
}
}
return false;
}
int main() {
int n, m;
cin >> n >> m;
// Taking input of the 2-D grid
vector < vector < char >> board(n, vector < char > (m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
char elem;
cin >> elem;
board[i].push_back(elem);
}
}
string word;
cin >> word;
// Calling the function
bool ans = exist(board, word);
if (ans)
cout << "true";
else
cout << "false";
return 0;
}
Input:
3
4
A
B
C
E
S
F
C
S
A
D
E
E
ABCCED
Output:
true
Complexity Analysis
Time Complexity: The time complexity of this approach will be O(N * M * 4 * length(‘word’)), where ‘N’ refers to the number of rows in the 2-D grid and ‘M’ refers to the number of columns in the 2-D grid. All the cells of the 2-D grid will be visited and traversed in all 4 directions, where ‘N’ and ‘M’ is the size of the grid so time complexity is O(M * N).
Space Complexity: The space complexity will be O(1) as we are not taking up any extra space here.