#63 Hard Time O(m·n·4^L) Space O(n·L) Animated
Word Search II
Find all words from a dictionary in a 2D board.
Approach: Trie + DFS Backtracking
Click play to start
Step 0 / 0
Press play to start the visualization.
1×
Steps
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
Solution — Trie + DFS Backtracking
O(m·n·4^L) O(n·L)
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)