Word Search

Given a rectangular board of English letters and a word, implement exist(board, word) and return true if consecutive letters of the word can be followed…

Given a rectangular board of English letters and a word, implement exist(board, word) and return true if consecutive letters of the word can be followed through horizontally or vertically adjacent cells. A cell may be used at most once in that path. Matching is case-sensitive. Return false when no such path exists; diagonal movement is not allowed.

- The board has 1..6 rows and 1..6 columns. - Each cell is one uppercase or lowercase English letter (ASCII A-Z or a-z). - The word contains 1..15 uppercase or lowercase English letters. - A word longer than the number of cells is still a valid input, with result false.

Example 1: input board = [["A","a"],["b","C"]], word = "AaC"; output true. The path follows A to a to C using orthogonal neighbors.

Example 2: input board = [["A","B"],["X","X"]], word = "ABA"; output false. Returning from B to the original A would reuse a cell.

Example 3: input board = [["A","X"],["X","B"]], word = "AB"; output false. A and B are diagonal, not orthogonal neighbors.

Category: Recursion. Topic: recursion. Difficulty: Hard. Patterns: backtracking.