Core Insight Store shared prefixes once so every character chooses the next edge in constant time.
Common Pitfall Keep an explicit end-of-word marker; reaching a node alone does not mean a word ends there.
Description
Find all words from a dictionary in a 2D board.
Constraints
- Time Complexity:
O(m·n·4^L) - Space Complexity:
O(n·L)
Tags
arraystringbacktrackingtriematrix
Implementation Plan Translate the invariant into these small, testable moves.
- Start at the root.
- Create or follow the edge for each character.
- Mark complete words explicitly.
- Use the same traversal rule for lookup.
class TrieNode:
def __init__(self):
self.children = {}
self.isWord = False
class Trie:
def __init__(self):
self.root = TrieNode()
def addWord(self, word):
cur = self.root
for c in word:
if c not in cur.children:
cur.children[c] = TrieNode()
cur = cur.children[c]
cur.isWord = True
class Solution:
def findWords(self, board, words):
trie = Trie()
for w in words: trie.addWord(w)
ROWS, COLS = len(board), len(board[0])
res, visit = set(), set()
def dfs(r, c, node, word):
if (r < 0 or c < 0 or r == ROWS or c == COLS or
(r, c) in visit or board[r][c] not in node.children):
return
visit.add((r, c))
node = node.children[board[r][c]]
word += board[r][c]
if node.isWord:
res.add(word)
dfs(r + 1, c, node, word)
dfs(r - 1, c, node, word)
dfs(r, c + 1, node, word)
dfs(r, c - 1, node, word)
visit.remove((r, c))
for r in range(ROWS):
for c in range(COLS):
dfs(r, c, trie.root, "")
return list(res)