- categories: Code, Interview Question, leetcode, Medium
- source: https://leetcode.com/problems/word-search-ii
- topics: Trie, String Manipulation, Backtracking
Description
Given an m x n board of characters and a list of strings words, return all words on the board.
Each word must 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 in a word.
Intuition
The Trie data structure allows for efficient prefix-based searching, reducing unnecessary traversals. Backtracking explores all possible paths on the board to match words.
Approach
- Construct a Trie: Build a Trie from the given list of words, where each node represents a character and stores the full word at the end of a valid path.
- Backtracking:
- For each cell in the board, check if it starts a word in the Trie.
- Recursively explore its neighbors while marking visited cells to avoid revisits.
- Add matched words to the result set and terminate paths that cannot yield further valid words.
Code
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
n, m = len(board), len(board[0])
directions = [[0,1],[0,-1],[1,0],[-1,0]]
trie = {}
for word in words:
pointer = trie
for char in word:
if char not in pointer:
pointer[char] = {}
pointer = pointer[char]
pointer['$'] = word
def backtrack(trie, used, i, j):
if '$' in trie:
ans.add(trie['$'])
if len(trie) == 1:
return
for dx, dy in directions:
x, y = i + dx, j + dy
if (x, y) in used or not (0 <= x < n and 0 <= y < m) or board[x][y] not in trie:
continue
used.add((x, y))
backtrack(trie[board[x][y]], used, x, y)
used.remove((x, y))
ans = set()
for i in range(n):
for j in range(m):
# All words are found
if len(ans) == len(words):
break
if not board[i][j] in trie:
continue
backtrack(trie[board[i][j]], {(i, j)}, i, j)
return list(ans)