Word Search - l

Moderate
0/80
Average time to solve is 30m
34 upvotes
Asked in companies
Morgan StanleyShareChatSprinklr

Problem statement

You are given a 2D board('N' rows and 'M' columns) of characters and a string 'word'.


Your task is to return true if the given word exists in the grid, else return false. The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring.


Note: 
The same letter cell should not be used more than once.
For Example: 
For a given word “design” and the given 2D board 
[[q’, ‘v’, ‘m’, ‘h’],
 [‘d’, ‘e’, ‘s’, ‘i’],
 [‘d’, ‘g’, ‘f’, ‘g’],
 [‘e’, ‘c’, ‘p’, ‘n’]]

The word design can be formed by sequentially adjacent cells as shown by the highlighted color in the 2nd row and last column.

board

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains a string 'word'.

The second line of input contains two single space-separated integers 'N' and 'M' representing the number of rows and columns of the grid respectively.

The next 'N' lines contain 'M' single space-separated characters each representing the elements in a row of the matrix.
Output Format: 
The only line contains either “true” or “false”.
Note: 
You do not need to print anything, it has already been taken care of. Just implement the function.
Sample Input 1:
coding
4 4
c z k l
o d i a
r g n m
m r s d
Sample Output 1:
true
Explanation For Sample Input 1:
For the given word, and grid we can construct from letters of sequentially adjacent cells as shown below:

board

Sample Input 2:
ninjas
4 4
c d k s
o d s i
d g n j
e r i n
Sample Output 2:
false
Constraints:
1 <= N <= 6
1 <= M <= 6
1 <= |word| <=20

Time Limit: 1 sec
Hint

Think of brute force and try to check for all the possibilities.

Approaches (1)
Backtracking

Approach:

To efficiently find a word on a board using a DFS approach, we can explore the board starting from each cell as the initial position for the first letter of the word. 

 

We check if the current cell matches the corresponding letter of the word. If it does, we mark the cell as visited and proceed to check the neighboring cells for the next letter. We continue this process recursively, incrementing the level of the word, until we either find the complete word or reach a dead-end.

 

If we successfully reach the level equal to the length of the word plus one, it means we have found the word on the board. Otherwise, if we exhaust all possible starting cells without finding the word, we conclude that it is not present on the board.

 

By utilizing DFS and backtracking, we efficiently explore different paths on the board, maximizing the chances of finding the desired word.

 

Algorithm:

  • Iterate over each cell on the board using nested loops.
  • If the current cell matches the first letter of the word, call the dfs function with the current position (i, j) and the starting index 0.
  • If dfs returns true, it means the word was found on the board, so return true.
  • If no matches were found, return false to indicate that the word is not present on the board.

The dfs function : 

  • If ‘k’ is equal to the length of the word, return true.
  • If the current position (i, j) is out of bounds or the current cell is marked as visited or the current cell doesn't match the letter at index k in the word, return false.
  • Store the value of the current cell in a temporary variable temp.
  • Mark the current cell as visited by setting board[i][j] to '#'.
  • Recursively call dfs for the neighboring cells with the index as 1 greater than the present one.
  • Restore the original value of the current cell by setting ‘board[i][j]’ back to temp.
  • Return true if any of the neighboring cells returned true (indicating the word was found in one of the paths), or false if none of them found the word.
Time Complexity

O(N*M*4L), where ‘N’ and ‘M’ are the dimensions of the board and ‘L’ is the length of the word 

 

In the worst case, when when the word is “AAA..AAN” and every cell in the board is 'A' we will start our search from every cell of the board that takes O(N*M) time. For each search, we will have 4 possible directions from the first character and the subsequent will have only 3 or fewer choices. But for an upper bound we can take 4 which will also be fine for large boards. So the search(dfs) function would take O(4^K) time for each cell.

Space Complexity

O(1)

 

We are not using any extra space.

Code Solution
(100% EXP penalty)
Word Search - l
Full screen
Console