Published: Sep 23, 2022
Introduction
This is a typical backtracking problem. Normally, a depth-first search works well. For the backtracking problem, how to get the state back to previous one is important. The solution here uses a special character as visited status and set it back when the process goes back.
Problem Description
Given an
m x n
grid of charactersboard
and a stringword
, return true if word exists in the grid.The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.
Constraints:
m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board
andword
consists of only lowercase and uppercase English letters.
Examples
Example 1
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true
Explanation:
[A] [B] [C] E
S F [C] S
A [D] [E] E
Example 2
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true
Explanation:
A B C E
S F C [S]
A D [E] [E]
Example 3
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false
Analysis
Since it is a backtracking problem, the depth-first approach is used here. As a visited state management, a special character ‘#’ is used. Save the current character on the board to make it back later. Set the special character to the cell and go deeper recursion with the suffix of the given word. When the suffix becomes empty, all character in the give word is found.
Solution
class WordSearch:
def exist(self, board: List[List[str]], word: str) -> bool:
m, n = len(board), len(board[0])
def dfs(row, col, suffix):
if not suffix:
return True
cur = board[row][col]
board[row][col] = '#'
up = row - 1 >= 0 and board[row - 1][col] == suffix[0] and dfs(row - 1, col, suffix[1:])
left = col - 1 >= 0 and board[row][col - 1] == suffix[0] and dfs(row, col - 1, suffix[1:])
right = col + 1 < n and board[row][col + 1] == suffix[0] and dfs(row, col + 1, suffix[1:])
down = row + 1 < m and board[row + 1][col] == suffix[0] and dfs(row + 1, col, suffix[1:])
if up or left or right or down:
return True
board[row][col] = cur
for row in range(m):
for col in range(n):
if board[row][col] == word[0] and dfs(row, col, word[1:]):
return True
return False
Complexities
- Time:
O(n * 3 ^ k)
– n: number of cells, k: length of the word, 3: one of four directions is where it comes from - Space:
O(k)