Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Approach to the Problem
2.1.
Implementation in C++
2.2.
Complexity Analysis
3.
Frequently Asked Questions 
3.1.
Can I solve this word search problem without making changes in the given 2-D grid?
3.2.
Can I solve this word search problem in less than O(N * M) time complexity?
4.
Conclusion
4.1.
Suggested Problems:
Last Updated: Mar 27, 2024
Hard

Word Search

Author Deeksha
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

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.

DSA

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.

 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions 

Can I solve this word search problem without making changes in the given 2-D grid?

Yes! You can. For this, you can make a 2-D grid ‘visited,’ and in this grid, you will keep marking the visited cells as true. But this will add up to your space complexity as you consume an N * M space for no reason.

Can I solve this word search problem in less than O(N * M) time complexity?

No! You can’t because in order to search your string you have to traverse all the cells of the 2-D grid at least once.

Conclusion

In this blog, we have solved the most frequently asked question word search. You will find many questions on this approach in online assessments of various tech- companies. We have also discussed the time and space complexity. 

Suggested Problems:

Also see, Word Beak Problem using Backtracking

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

If you feel that this blog has helped you in any way, then please do share it with your friends. Happy Coding!

Cheers!

Previous article
Rat in a Maze
Next article
Valid Sudoku
Live masterclass