Medium · Backtracking

Word Search

Given an m × n grid of letters board and a string word, return true if word can be spelled by a path of horizontally or vertically adjacent cells that uses each cell at most once, and false otherwise.

Examples

Example 1

{
  "board": [
    ["A", "B", "C", "E"],
    ["S", "F", "C", "S"],
    ["A", "D", "E", "E"]
  ],
  "word": "ABCCED"
}

Output: true

Example 2

{
  "board": [
    ["A", "B", "C", "E"],
    ["S", "F", "C", "S"],
    ["A", "D", "E", "E"]
  ],
  "word": "ABCB"
}

Output: false

Rebuild it in the studio

Read every interview problem free. Ten rooms need no account. A token opens a problem in full — Pro never counts.