Recursion and Backtracking Searching with constraints
330. Word Search
You are given a grid of lowercase letters, board, as a list of strings. board[i] is row i, and
board[i][j] is the letter in row i, column j. You are also given a string word. Return true if a
path through the grid spells word, and false otherwise.
A path starts at any cell and moves one step at a time to the cell directly above, below, left or right
of the current one. Diagonal steps are not allowed. The letters along the path, in order, must spell word,
and the path cannot use the same cell twice.
Example 1
Input: board = ["gats", "drop", "enik"], word = "garden"
trueExplanation: The path goes g (row 0, column 0), a (0, 1), r (1, 1), d (1, 0), e (2, 0) and n (2, 1). It turns three times, which is allowed.
Example 2
Input: board = ["gats", "drop", "enik"], word = "pop"
falseExplanation: The board has only one p, at row 1, column 3. Spelling "pop" would use that cell twice.
Example 3
Input: board = ["ab", "cd"], word = "acdb"
trueExplanation: The path goes down from a to c, right to d, and up to b. It ends next to where it started, which is fine, because no cell is used twice.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ board.length ≤ 121 ≤ board[i].length ≤ 12, and every row has the same length1 ≤ word.length ≤ 15boardandwordhold only lowercase English letters.
Clarifying questions
What you would ask an interviewer before writing any code.