Word Search

MediumBacktrackingword-search

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 constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example 1:

Input:
board = [
  ["A","B","C","D"],
  ["S","A","A","T"],
  ["A","C","A","E"]
],
word = "CAT"

Output: true

Recommended time and space complexity

Time complexity: O(N * M * 4^L), where N and M are the grid dimensions, L is the word length. Space complexity: O(L), where L is the word length.


Hint 1

Try using backtracking. Start by searching for the first letter of the word in the grid.


Hint 2

After finding the first letter, explore all possible paths by moving in four directions (up, down, left, right).


Hint 3

Use an additional data structure (like a set) to track already visited cells to avoid reusing them.

This problem tests skills in working with 2D arrays, recursion, and backtracking. It helps improve understanding of graph and matrix traversal algorithms, and develops the ability to optimize recursive solutions.
solution.js · saved

Input

[["A","B","C","D"],["S","A","A","T"],["A","C","A","E"]], "CAT"

Expected Output

true