Word Search

Backtracking, problem 6 of 7

Word Search

Medium

LC #79

griddfspruning

Not attempted yet

Given a grid of letters board and a string word, return True if the word can be spelled by a path of cells where each step moves up, down, left or right. A cell may be used at most once in the path.

Example 1

Input: board = [["C","A","T"],
                ["O","R","S"],
                ["D","E","N"]],
       word = "CODE"
Output: True

C (0,0) → O (1,0) → D (2,0) → E (2,1).

Example 2

Input: same board, word = "STAR"
Output: True

Example 3

Input: same board, word = "CAC"
Output: False

There's only one C, and it can't be used twice.

Constraints

  • 1 ≤ rows, cols ≤ 6
  • 1 ≤ len(word) ≤ 15
  • Letters are English letters (case matters).

Follow-up: can you prune so that hopeless searches stop early?

Python

Loading draft…

Test results

10 tests available

No results yet

Run tests your code against the examples; Submit runs the hidden tests too.

3 examples, 7 hidden

Run examples, then submit all tests.