You are given a rectangular board of letters, one string per row, and a word. Decide whether the word can be traced on the board by starting anywhere and stepping only to horizontally or vertically adjacent cells, using no cell more than once in the trace.
Examples
Example 1:
Input: board = ["ABCE","SFCS","ADEE"], word = "ABCCED"
Output: true
Example 2:
Input: board = ["ABCE","SFCS","ADEE"], word = "SEE"
Output: true
Example 3:
Input: board = ["ABCE","SFCS","ADEE"], word = "ABCB"
Output: false
Explanation: the B would have to be reused.
Example 4:
Input: board = ["AB","CD"], word = "ABDC"
Output: true
Explanation: a path may snake — right, down, left.
Constraints
1 <= rows, columns <= 6
1 <= word.length <= 15
Board and word consist of uppercase English letters.
Prerequisites
Backtracking — choose, recurse, undo. The undo is what makes the rest correct. Pruning: cutting a branch the moment it cannot lead anywhere.
How to think about it
1. DFS With an Undo Optimal
Intuition
Try every cell as a starting point, then walk neighbours matching the word letter by letter. The only subtlety is the mark: a cell must be off-limits for the duration of a path and available again afterwards, because a different path may legitimately use it. That unmark on the way out is the whole problem — "ABCB" is in the tests because it is what catches a missing one.
Algorithm
1. For each cell, start a DFS at word position 0. 2. Out of bounds, already used, or a letter mismatch: fail this branch. 3. Mark the cell, try all four neighbours for the next letter. 4. Unmark before returning. 5. Reaching the word's end is success.
Time & Space
Time O(cells x 3^len) worst case — three onward directions after the first step. Space O(len) for the recursion plus the used grid.