1class TrieNode:
2 def __init__(self):
3 self.children = {}
4 self.word = None
5
6def findWords(board, words):
7 def dfs(r, c, node):
8 if node.word:
9 result.append(node.word)
10 node.word = None
11
12 char = board[r][c]
13 board[r][c] = '#'
14
15 for dr, dc in dirs:
16 nr, nc = r + dr, c + dc
17 if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != '#':
18 next_char = board[nr][nc]
19 if next_char in node.children:
20 dfs(nr, nc, node.children[next_char])
21
22 board[r][c] = char
23
24 # Build Trie
25 root = TrieNode()
26 for word in words:
27 node = root
28 for char in word:
29 if char not in node.children:
30 node.children[char] = TrieNode()
31 node = node.children[char]
32 node.word = word
33
34 rows, cols = len(board), len(board[0])
35 result = []
36 dirs = [(1,0),(-1,0),(0,1),(0,-1)]
37
38 for r in range(rows):
39 for c in range(cols):
40 if board[r][c] in root.children:
41 dfs(r, c, root.children[board[r][c]])
42
43 return result| Variable | Value |
|---|---|
board | Matrix(4x4) [["o","a","a","n"]...] |
words | ["oath","pea","eat","rain"] |
root | - |
word | - |
dirs | - |
result | - |
rows | - |
cols | - |
r | - |
c | - |
| Depth | Function Call |
|---|---|
| 1 | findWords([["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], ["oath","pea","eat","rain"]) |
1class TrieNode:
2 def __init__(self):
3 self.children = {}
4 self.word = None
5
6def findWords(board, words):
7 def dfs(r, c, node):
8 if node.word:
9 result.append(node.word)
10 node.word = None
11
12 char = board[r][c]
13 board[r][c] = '#'
14
15 for dr, dc in dirs:
16 nr, nc = r + dr, c + dc
17 if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != '#':
18 next_char = board[nr][nc]
19 if next_char in node.children:
20 dfs(nr, nc, node.children[next_char])
21
22 board[r][c] = char
23
24 # Build Trie
25 root = TrieNode()
26 for word in words:
27 node = root
28 for char in word:
29 if char not in node.children:
30 node.children[char] = TrieNode()
31 node = node.children[char]
32 node.word = word
33
34 rows, cols = len(board), len(board[0])
35 result = []
36 dirs = [(1,0),(-1,0),(0,1),(0,-1)]
37
38 for r in range(rows):
39 for c in range(cols):
40 if board[r][c] in root.children:
41 dfs(r, c, root.children[board[r][c]])
42
43 return result