Find a Word in a Letter Grid

MediumMatrixBacktrackingDfs183 tests

You are given a grid board of letters and a string word. Each cell of the grid holds one lowercase letter, as a string of length 1.

You can build a word by starting at any cell and then moving, one step at a time, to a cell that is directly up, down, left or right of the current cell. Diagonal moves are not allowed. The letters of the cells you visit, in order, spell the word.

In one path, each cell can be used at most once.

Return true if word can be built in this way, and false if it cannot.

Hint: try every cell as a start. From a cell, go deeper only if the cell has the next letter you need. Mark the cell as used while you search from it, and unmark it when you go back (backtracking).

Examples

Example 1

Input:: [["m","a","p"],["e","t","s"],["r","o","w"]], "meta"
Output:: true

Start at "m" (row 0, col 0). Go down to "e", right to "t", and up to "a". The path spells "meta" and uses four different cells.

Example 2

Input:: [["s","e"],["k","n"]], "sees"
Output:: false

The grid has only one "s" and one "e". The word needs each of them twice, but a cell can be used only once in a path.

Example 3

Input:: [["c","a","t","s"]], "tac"
Output:: true

Start at "t" (col 2) and move left twice: "t", "a", "c". A path can go in any direction.

Constraints

1 <= board.length <= 5
1 <= board[i].length <= 5, and every row has the same length.
board[i][j] is a single lowercase English letter.
1 <= word.length <= 8
word has only lowercase English letters.

Run checks your code against the 3 examples. Submit checks it against all 183 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.