Given an m x n grid of letters board and a string word, return true if word can be traced in the grid. You trace a word by starting at any cell and moving one step up, down, left or right for each next letter. The same cell cannot be used twice in one word.
- 1 <= m, n <= 6
- 1 <= word.length <= 15
- board and word contain only English letters
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Every path in the grid could be a candidate, so we need a search. From each starting cell, DFS tries the four neighbours for the next letter and abandons a path the moment a letter does not match. The only extra state is "which cells are on the current path"; temporarily replacing the cell with a marker and putting the letter back after the call does this in O(1) space per cell, which is classic backtracking.
Algorithm
- For each cell
(r, c), calldfs(r, c, 0); returntrueif any call succeeds. - In
dfs(r, c, i): ifi == len(word)returntrue. - If
(r, c)is out of bounds orboard[r][c] != word[i], returnfalse. - Save the letter, set
board[r][c] = "#", and recurse into the four neighbours withi + 1. - Restore the letter and return whether any neighbour succeeded.
O(m * n * 3^L), where L is the word lengthSpace: O(L) recursion depthfalse immediately. Also reversing the word when its last letter is rarer than its first cuts the search a lot.class Solution: def exist(self, board: List[List[str]], word: str) -> bool: rows, cols = len(board), len(board[0])Β def dfs(r, c, i): if i == len(word): return True if r < 0 or c < 0 or r >= rows or c >= cols or board[r][c] != word[i]: return False saved = board[r][c] board[r][c] = "#" # mark as used on this path found = (dfs(r + 1, c, i + 1) or dfs(r - 1, c, i + 1) or dfs(r, c + 1, i + 1) or dfs(r, c - 1, i + 1)) board[r][c] = saved # undo the mark return foundΒ for r in range(rows): for c in range(cols): if dfs(r, c, 0): return True return False