Description
Find all distinct dictionary words traceable through orthogonally adjacent lowercase board cells without cell reuse. Return each word once.
Solution
def find_words(board, words):
root = {}
for word in words:
node = root
for c in word:
node = node.setdefault(c,{})
node['#'] = word
result = []
def walk(r,c,node):
if not (0 <= r < len(board) and 0 <= c < len(board[0])):
return
char = board[r][c]
if char not in node:
return
child = node[char]
word = child.pop('#',None)
if word is not None:
result.append(word)
board[r][c] = '!'
for dr,dc in ((1,0),(-1,0),(0,1),(0,-1)):
walk(r+dr,c+dc,child)
board[r][c] = char
for r in range(len(board)):
for c in range(len(board[0])):
walk(r,c,root)
return resultExamples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[[["a","b"],["c","d"]],["ab","ac","ad"]]- Output
["ab","ac"]
ab and ac follow edges; ad would require a diagonal.
Example 2
- Input
[[["a"]],["a","aa"]]- Output
["a"]
A cell cannot be reused to form aa.
Example 3
- Input
[[["z"]],["x"]]- Output
[]
The board has no x.
Approach
Build a trie for the dictionary and explore board paths only while their prefix exists. Clear a found terminal to deduplicate results.
Time & space
O(S + R C 4^L) upper-bound time; O(S + L) auxiliary space, excluding output, for total dictionary characters S and maximum word length L.