Word Search
Explore the backtracking approach to solve the word search problem where you find a given word in a character grid by connecting adjacent cells only once. Understand the constraints and implement a solution that tests your skills in combinatorial problem solving and sequential adjacency checks.
We'll cover the following...
Statement
Given an m x n grid of characters, board, and a string word, return TRUE if word exists in the grid.
The word can be formed by connecting letters of sequentially adjacent cells. The cells are considered sequentially adjacent when neighbors are either horizontally or vertically neighbors. Each cell can be used only once while forming the word.
Constraints:
mboard.lengthnboard[i].length, whereimm, nword.lengthboardandwordconsist of only lowercase and uppercase English letters.
Examples
Understand the problem
Let’s take a moment to make sure you've correctly understood the problem. The quiz below helps you check if you're solving the correct problem:
Word Search
Can we find the word in the given grid?
[['K', 'I', 'C', 'D', 'L', 'J', 'M', 'R']
['V', 'M', 'S', 'P', 'C', 'F', 'A', 'G']
['C', 'A', 'G', 'D', 'J', 'O', 'L', 'O']
['Q', 'Z', 'N', 'T', 'F', 'X', 'C', 'T']
['R', 'L', 'A', 'N', 'I', 'R', 'G', 'D']
['J', 'A', 'W', 'Y', 'M', 'O', 'U', 'A']
['Z', 'A', 'P', 'D', 'R', 'C', 'S', 'D']
['Y', 'V', 'A', 'F', 'P', 'L', 'Z', 'T']]
Yes
No
Figure it out!
We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.
Try it yourself
Implement your solution in the following coding playground.
#include <iostream>#include <string>#include <vector>#include <cctype>// Apply backtracking on every element to search the required wordbool WordSearch(vector<vector<char>> grid, string word){// Replace this placeholder return statement with your codereturn false;}