backtracking · Problem 2 of 2

Word Search

medium
Amazon logoAmazon
Google logoGoogle
Meta logoMeta
Microsoft logoMicrosoft
Bloomberg logoBloomberg

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 (horizontally or vertically neighboring). The same letter cell may not be used more than once in a single word path.

exist([
  ["A","B","C","E"],
  ["S","F","C","S"],
  ["A","D","E","E"]
], "ABCCED") -> true

exist([
  ["A","B","C","E"],
  ["S","F","C","S"],
  ["A","D","E","E"]
], "SEE")    -> true

exist([
  ["A","B","C","E"],
  ["S","F","C","S"],
  ["A","D","E","E"]
], "ABCB")   -> false

Your solution

Runs your code and animates it without grading anything. Change the input to see what it does on a case the tests do not cover.

Running is free — Submit is what records it. Or press ⌘↩

Tests

4 cases, 1 hidden
calltypeexpectedresult
exist([["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "ABCCED")word exists horizontally and verticallytrue—
exist([["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "SEE")word exists shorttrue—
exist([["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "ABCB")reusing same cell invalidfalse—
withheldhiddenwithheld—

Hidden cases run too — their inputs aren't listed here, so aim for a general solution rather than one fitted to the cases above.

Complexity

target time
O(m × n × 4^L) where L is word length
target space
O(L) recursion depth

In-place cell marking provides O(1) auxiliary matrix space while backtracking.

Hints

Stuck? Hints open one at a time, each giving a little more away.

3 hints left