The grid board holds one letter in each cell. Decide whether you can spell word by tracing a path through the grid: start on any cell, and step each time to a cell directly above, below, left or right of the current one (not diagonally). The cells along the path, in order, must spell word, and no cell may be used twice in the same path.
Return true if such a path exists, otherwise false. Upper- and lower-case letters are different: a does not match A.
Start at C in the top-left corner, step down to O, right to D, right to E.
L, I, N run along the bottom row, then the path turns up to E and right to S.
CODE can be traced, but the grid has only one D, and a cell can't be used a second time.
Constraints
m == board.lengthn == board[i].length1 <= m, n <= 61 <= word.length <= 15board and word are made of upper- and lower-case English letters only.Try every cell as a start and extend the path one neighbour at a time, backing up when the next letter doesn't match (backtracking). Mark the cells on the current path so none is reused, and unmark them as you back up.
Spelling the word is a walk: pick a starting cell holding the first letter, then keep stepping to a neighbour that holds the next letter. At each step there are at most four neighbours to try, and usually only one or two hold the right letter, so most branches die after a step or two.
Time O(m · n · 3^L)Space O(m · n + L)
The full walkthrough and code are part of Premium
true