Why it works
- A call answers one question: can word[k:] be read starting at this cell? Its own letter must match, and then one neighbour must answer yes for word[k + 1:], so a true at the top means a real path.
- While a cell is on the path it holds #, which matches no letter, so a call that comes back to it turns itself away: no cell is read twice.
- Every call puts its letter back before it returns, so a dead end leaves the board as it found it and the cell is free for other paths.
Complexity
Time O(m × n × 3ᴸ), where L is the length of the word: each of the m × n cells may start a path, and after the first step each cell has at most 3 neighbours that are not the one it came from. Memory O(L): the call stack is at most L deep, and the marks live on the board itself.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗