题目重点：字典前缀树、路径内visited、终止去重与安全删除空支，明确标准题训练和未知变体。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 矩形单字符网格，四邻接，单条路径不复用格子，返回可找到的不同非空word。
- 结果按字典序，重复词去重、空词忽略；这些是训练口径。题目变种是否允许斜向/重复使用/路径输出待核。
解题路线
- Trie把字典共有前缀存一份，从每格出发沿当前字母分支前进。不存在前缀立即剪枝，不给每个词独立扫描完整网格。终止标记用独立object避免与任意字符键冲突。
- visited只属于当前路径，进入添加、回退删除；全局visited会让另一条路径无法使用同一个格子。代码不修改board，状态局限本次搜索。
- 发现word后pop终止标记保证全局每词一次，仍保留子节点以找到更长词。prefix词a和ab都可存在，找到a不能把整个a分支删掉。
- 如果回溯后该Trie节点无终止/无子分支，说明其子树所有词均已找到，可以从parent删除；剩余word不受影响。这是只需要每词一次时的优化，若要所有路径不能同样剪。
- 正确性：所有返回词来自Trie终止且一条合法网格路径；未找到的可行词在首次找到前其完整前缀必保留，DFS枚举相邻未用格，不能被空支删除误剪。
- 深长路径递归有栈限制，需要按正式word/board规模改显式DFS；算法共享prefix降低重复搜索，却不意味着最坏全搜索多项式。
手动走一遍
网格[['a','b']]字典['a','ab','aba','ab']，返回['a','ab']；aba不能再次走回a格。3,090网格/字典集合与独立枚举所有路径字符串对照，另Unicode案例及输入不变检查通过。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def find_words(board, words):
"""Four neighbors, no cell reuse per path, unique lexicographically sorted output."""
rows = len(board)
cols = len(board[0]) if rows else 0
if any(len(row) != cols for row in board):
raise ValueError("rectangular board required")
end = object()
root = {}
for word in set(words):
if not word: # Explicit training policy: ignore empty dictionary entries.
continue
node = root
for char in word:
node = node.setdefault(char, {})
node[end] = word
result, used = [], set()
def dfs(r, c, parent):
char = board[r][c]
node = parent.get(char)
if node is None:
return
word = node.pop(end, None)
if word is not None:
result.append(word)
used.add((r, c))
for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in used:
dfs(nr, nc, node)
used.remove((r, c))
if not node:
del parent[char]
for r in range(rows):
for c in range(cols):
dfs(r, c, root)
return sorted(result)
复杂度
建Trie O(S)，S为字典字符总量；网格V格、最长word长ℓ，保守搜索O(V·4^ℓ)，无回头可细化约O(V·4·3^(ℓ−1))，实际前缀剪枝更小。Trie O(S)、路径O(min(V,ℓ))与输出排序成本另计。
易错点与追问
容易失分的边界
- visited全局不回退。
- 找到短prefix删整支。
- 删除终止后仍声称返回所有路径。
- Trie优化就说最坏O(V+S)。
- 未知变种当标准原题。
继续深挖
- 需要每词所有坐标路径怎么改去重？
- 允许格子重复时要加什么长度界？
- 极大字典怎样按board字符预筛？
- 深网格怎样改显式回溯？
