单词搜索 II 图解题解

这道题到底在问什么

输入

board = [["o","a","t"],["a","p","e"],["t","e","a"]]，words = ["oat","pea","tea"]

输出

["oat","pea","tea"]（三个都能拼出）

最优解：一步一步想明白

1. 3记住两条主线：棋盘的 DFS 和字典树的指针「绑在一起同步走」；字典树没分支就剪枝、有结束标记就收词。下面每一帧都在套这套规则。
2. 4先把要找的三个单词 oat、pea、tea 压成一棵字典树（共享公共前缀），再让搜索从棋盘每个格子出发。下面演示几个有代表性的起点。
3. 5格子的字母 o 正好对上字典树里的分支，落子选中它（橙色是刚走到的格子，浅色是路径上之前选过的）。当前拼出的前缀是 "o"，沿着它接着往四周找下一个字母。
4. 6格子的字母 a 正好对上字典树里的分支，落子选中它（橙色是刚走到的格子，浅色是路径上之前选过的）。当前拼出的前缀是 "oa"，沿着它接着往四周找下一个字母。
5. 7格子的字母 t 正好对上字典树里的分支，落子选中它（橙色是刚走到的格子，浅色是路径上之前选过的）。当前拼出的前缀是 "oat"，沿着它接着往四周找下一个字母。
6. 8走到这里，字典树的这个节点挂着结束标记，意味着路径上的字母刚好拼成了目标单词 "oat"！把它收进答案。为了不重复收录，把这个单词从字典树上摘掉。
7. 9从这里往这个方向探一步，字母是 e。字典树里当前节点没有 e 这条分支，说明 "oate" 不可能拼成任何目标单词，直接掐断这条路，不再往下走。
8. 10从这里往这个方向探一步，字母是 p。字典树里当前节点没有 p 这条分支，说明 "oap" 不可能拼成任何目标单词，直接掐断这条路，不再往下走。
9. 11格子的字母 a 正好对上字典树里的分支，落子选中它（橙色是刚走到的格子，浅色是路径上之前选过的）。当前拼出的前缀是 "oa"，沿着它接着往四周找下一个字母。
10. 12从这里往这个方向探一步，字母是 p。字典树里当前节点没有 p 这条分支，说明 "oap" 不可能拼成任何目标单词，直接掐断这条路，不再往下走。
11. 13格子的字母 t 正好对上字典树里的分支，落子选中它（橙色是刚走到的格子，浅色是路径上之前选过的）。当前拼出的前缀是 "oat"，沿着它接着往四周找下一个字母。
12. 14从这里往这个方向探一步，字母是 e。字典树里当前节点没有 e 这条分支，说明 "oate" 不可能拼成任何目标单词，直接掐断这条路，不再往下走。
13. 15格子的字母 p 正好对上字典树里的分支，落子选中它（橙色是刚走到的格子，浅色是路径上之前选过的）。当前拼出的前缀是 "p"，沿着它接着往四周找下一个字母。
14. 16格子的字母 e 正好对上字典树里的分支，落子选中它（橙色是刚走到的格子，浅色是路径上之前选过的）。当前拼出的前缀是 "pe"，沿着它接着往四周找下一个字母。
15. 17格子的字母 a 正好对上字典树里的分支，落子选中它（橙色是刚走到的格子，浅色是路径上之前选过的）。当前拼出的前缀是 "pea"，沿着它接着往四周找下一个字母。
16. 18走到这里，字典树的这个节点挂着结束标记，意味着路径上的字母刚好拼成了目标单词 "pea"！把它收进答案。为了不重复收录，把这个单词从字典树上摘掉。
17. 19从这里往这个方向探一步，字母是 e。字典树里当前节点没有 e 这条分支，说明 "peae" 不可能拼成任何目标单词，直接掐断这条路，不再往下走。
18. 20从这里往这个方向探一步，字母是 t。字典树里当前节点没有 t 这条分支，说明 "pet" 不可能拼成任何目标单词，直接掐断这条路，不再往下走。
19. 21从这里往这个方向探一步，字母是 a。字典树里当前节点没有 a 这条分支，说明 "pa" 不可能拼成任何目标单词，直接掐断这条路，不再往下走。
20. 22格子的字母 e 正好对上字典树里的分支，落子选中它（橙色是刚走到的格子，浅色是路径上之前选过的）。当前拼出的前缀是 "pe"，沿着它接着往四周找下一个字母。
21. 23格子的字母 a 正好对上字典树里的分支，落子选中它（橙色是刚走到的格子，浅色是路径上之前选过的）。当前拼出的前缀是 "pea"，沿着它接着往四周找下一个字母。
22. 24从这里往这个方向探一步，字母是 e。字典树里当前节点没有 e 这条分支，说明 "peae" 不可能拼成任何目标单词，直接掐断这条路，不再往下走。
23. 25从这里往这个方向探一步，字母是 t。字典树里当前节点没有 t 这条分支，说明 "pet" 不可能拼成任何目标单词，直接掐断这条路，不再往下走。
24. 26从这里往这个方向探一步，字母是 a。字典树里当前节点没有 a 这条分支，说明 "pa" 不可能拼成任何目标单词，直接掐断这条路，不再往下走。
25. 27格子的字母 t 正好对上字典树里的分支，落子选中它（橙色是刚走到的格子，浅色是路径上之前选过的）。当前拼出的前缀是 "t"，沿着它接着往四周找下一个字母。
26. 28从这里往这个方向探一步，字母是 a。字典树里当前节点没有 a 这条分支，说明 "ta" 不可能拼成任何目标单词，直接掐断这条路，不再往下走。
27. 29格子的字母 e 正好对上字典树里的分支，落子选中它（橙色是刚走到的格子，浅色是路径上之前选过的）。当前拼出的前缀是 "te"，沿着它接着往四周找下一个字母。
28. 30从这里往这个方向探一步，字母是 p。字典树里当前节点没有 p 这条分支，说明 "tep" 不可能拼成任何目标单词，直接掐断这条路，不再往下走。
29. 31格子的字母 a 正好对上字典树里的分支，落子选中它（橙色是刚走到的格子，浅色是路径上之前选过的）。当前拼出的前缀是 "tea"，沿着它接着往四周找下一个字母。
30. 32走到这里，字典树的这个节点挂着结束标记，意味着路径上的字母刚好拼成了目标单词 "tea"！把它收进答案。为了不重复收录，把这个单词从字典树上摘掉。
31. 33从这里往这个方向探一步，字母是 e。字典树里当前节点没有 e 这条分支，说明 "teae" 不可能拼成任何目标单词，直接掐断这条路，不再往下走。
32. 34所有起点搜完，棋盘上能拼出的目标单词是 oat、pea、tea，一共 3 个，这就是最终答案。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

def findWords(board, words):
    trie = {}                       # 用嵌套字典当字典树
    for w in words:
        node = trie
        for ch in w: node = node.setdefault(ch, {})
        node['$'] = w               # 结束标记存整词
    R, C, res = len(board), len(board[0]), []
    def dfs(r, c, node):
        ch = board[r][c]
        nxt = node.get(ch)
        if nxt is None: return       # 无分支 → 剪枝
        if '$' in nxt:
            res.append(nxt.pop('$')) # 收词并去重
        board[r][c] = '#'            # 标记已用
        for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
            nr, nc = r+dr, c+dc
            if 0<=nr<R and 0<=nc<C and board[nr][nc] != '#':
                dfs(nr, nc, nxt)
        board[r][c] = ch            # 回溯还原
    for r in range(R):
        for c in range(C): dfs(r, c, trie)
    return res

struct Node { Node* ch[26]={}; string word; };
vector<string> findWords(vector<vector<char>>& b, vector<string>& ws){
    Node* root = new Node();
    for (auto& w : ws){ Node* n=root;
        for (char c: w){ int k=c-'a'; if(!n->ch[k]) n->ch[k]=new Node(); n=n->ch[k]; }
        n->word = w; }
    int R=b.size(), C=b[0].size(); vector<string> res;
    function<void(int,int,Node*)> dfs=[&](int r,int c,Node* n){
        char ch=b[r][c]; if(ch=='#') return;
        Node* nx=n->ch[ch-'a']; if(!nx) return;   // 剪枝
        if(!nx->word.empty()){ res.push_back(nx->word); nx->word.clear(); }
        b[r][c]='#';
        int dr[]={1,-1,0,0}, dc[]={0,0,1,-1};
        for(int k=0;k<4;k++){ int nr=r+dr[k],nc=c+dc[k];
            if(nr>=0&&nr<R&&nc>=0&&nc<C) dfs(nr,nc,nx); }
        b[r][c]=ch;                                // 回溯
    };
    for(int r=0;r<R;r++) for(int c=0;c<C;c++) dfs(r,c,root);
    return res;
}

class Node { Node[] ch = new Node[26]; String word; }
public List<String> findWords(char[][] b, String[] ws){
    Node root = new Node();
    for (String w : ws){ Node n=root;
        for (char c: w.toCharArray()){ int k=c-'a';
            if(n.ch[k]==null) n.ch[k]=new Node(); n=n.ch[k]; }
        n.word = w; }
    List<String> res = new ArrayList<>();
    int R=b.length, C=b[0].length;
    int[][] DIR={{1,0},{-1,0},{0,1},{0,-1}};
    java.util.function.BiConsumer<int[],Node> dummy=null;
    // 用递归方法 dfs(r,c,node)：取 nx=node.ch[b[r][c]-'a']
    // nx==null 剪枝；nx.word!=null 收词并置空；标 '#' 后回溯还原
    for(int r=0;r<R;r++) for(int c=0;c<C;c++) dfs(b,r,c,root,res,R,C,DIR);
    return res;

复杂度

面试官可能追问