Word Search
Given a 2D grid of characters and a string word, return True if the word exists in the grid. The word can be constructed from sequentially adjacent cells (horizontally or vertically). Each cell may only be used once.
Input: grid rows on separate lines, then the word.
Example:
ABCE SFCS ADEE ABCB
True
- The input grid is searched for the word "ABCCED" (implied, not given in the sample input) in all eight possible directions (up, down, left, right, and four diagonals), but only horizontal and vertical directions are considered in this problem.
- Starting from each cell, the algorithm checks if the current cell matches the first character of the word, then moves to the adjacent cell (horizontally or vertically) to check the next character.
- The word "ABCCED" is found in the grid by starting at the cell containing 'A', then moving right to 'B', down to 'C', down to 'C', down to 'E', and down to 'D'.
- The final output is
Truebecause the word is found in the grid.
Constraints:
- 1 <= rows, cols <= 6
- 1 <= len(word) <= 15
- board and word consist of uppercase and lowercase English letters
Background Knowledge
The "Word Search" problem falls under the category of Graphs & Search, which involves traversing through a data structure to find a specific pattern or solution. In this case, the data structure is a 2D grid of characters, and the goal is to search for a given word within this grid. The word can be constructed from sequentially adjacent cells, which means that each character in the word must be found in a cell that is directly horizontal or vertical to the previous character. This constraint implies that the search algorithm needs to explore the grid in a way that respects these adjacency relationships.
The concept of adjacency is crucial in this problem, as it defines how cells in the grid are connected to each other. In a 2D grid, each cell has four adjacent cells: one above, one below, one to the left, and one to the right. The search algorithm needs to consider these adjacency relationships when exploring the grid to find the word. Additionally, the problem statement mentions that each cell may only be used once, which means that the algorithm needs to keep track of visited cells to avoid revisiting them and entering an infinite loop.
The "Word Search" problem can be solved using various search algorithms, including Depth-First Search (DFS) and Breadth-First Search (BFS). However, due to the constraint that each cell may only be used once, DFS is a more natural fit for this problem. DFS involves exploring the grid by traversing as far as possible along each branch before backtracking, which allows the algorithm to efficiently search for the word while avoiding revisits to the same cell.
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
Editor locked
The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.