All problems

Word Search

Medium · backtracking

You are given a grid of lowercase letters, board, and a string word. Return True if word can be spelled by walking through the grid, and False otherwise.

The walk starts on any cell and moves one step at a time to a cell that shares an edge with the current one (up, down, left or right, never diagonally). The letters you step on, in order, must spell word. A cell may be used at most once in a single walk, but a different walk is free to use it again.

word always has at least one letter, so a single matching cell is enough for a one-letter word.

Examples

Example 1

Input: board = [["a","b","c","e"], ["s","f","c","s"], ["a","d","e","e"]], word = "abcced"

Output: True

Start at the top left a, go right through b and c, then down to the second c, down to e, and left to d.

Example 2

Input: board = [["a","b","c","e"], ["s","f","c","s"], ["a","d","e","e"]], word = "see"

Output: True

The s at the end of row 1, then the two e cells below it in order.

Example 3

Input: board = [["a","b","c","e"], ["s","f","c","s"], ["a","d","e","e"]], word = "abcb"

Output: False

The walk a, b, c is fine, but the last letter needs the same b again, and a cell cannot be reused.

Constraints