TikTok OA 面试真题解析：Word Search II（DFS + Trie）

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Given an m x n board of characters and a list of words, return all words on the board.

Example

Input: board = [["o","a","a","n"],
                ["e","t","a","e"],
                ["i","h","k","r"],
                ["i","f","l","v"]], words = ["oath","oathes","pea","eat","rain"]

Output: ["eat","oath","oathes"]

这道题是典型的单词搜索扩展版：在二维字符网格中，用上下左右相邻的格子拼出字典里的多个单词，而且同一个格子在同一个单词中不能重复使用。标准做法是用 Trie 先把所有单词建成前缀树，再对棋盘每个位置做 DFS 回溯，沿着 Trie 的前缀不断向下搜索，这样可以快速剪枝，避免对每个单词单独暴力搜索。示例中可以从 board 中找到 eat、oath 和 oathes，说明我们需要同时支持单词匹配与前缀延伸。