61. Word Search

Given a grid of n x m dimension grid of characters board and a string word.The word can be created by assembling the letters of successively surrounding cells, whether they are next to each other vertically or horizontally. It is forbidden to use the same letter cell more than once.

Return true if the word exists in the grid otherwise false.

Example 1:

Input : board = [ ["A", "B", "C", "E"] , ["S" ,"F" ,"C" ,"S"] , ["A", "D", "E", "E"] ] , word = "ABCCED"

Output : true

Explanation : The word is coloured in yellow.

Example 2:

Input : board = [["A", "B", "C", "E"] , ["S", "F", "C", "S"] , ["A", "D", "E", "E"]] , word = "SEE"

Output : true

Explanation : The word is coloured in yellow.

Now Your Turn!

Pick the correct output for the given input

Input : board = [["A", "B", "C", "E"] , ["S", "F", "C", "S"] , ["A", "D", "E", "E"]] , word = "ABCB"

Still unsure what the problem is asking ?

Let’s go through a few more examples, step by step, to make it clearer.

Constraints:

  • n = board.length
  • m = board[i].length
  • 1 <= n, m <=6
  • 1 <= word.length <= 15
  • board and word consist of only lowercase and uppercase English letters.

Hints

Frequently Occurring Doubts

Interview Follow-up Questions

Fun Facts

0
class Solution {
public:
bool exist(vector<vector<char> >& board, string word) {
//your code goes here
}
};
Test Case

Input:

Board
Word