212 单词搜索 II

题目描述#

给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words，返回所有二维网格上的单词。

单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中"相邻"单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

思路#

困难题？别怕别怕，咱拆开看其实是"老朋友 + 老朋友"～

最笨的思路就是对 words 里每个单词都在网格上 DFS 一遍——单词一多就原地爆炸啦。咱得换个脑子：把所有单词先塞进一棵前缀树，然后只走一遍网格，让前缀树替我们同步剪枝。

具体打法是这样的：

建前缀树：把 words 里每个单词按字母挂到 Trie 上，在单词终点节点直接存一个 word 字段（存完整字符串本体）。这样一旦走到这个节点，答案直接抓走，不用回溯拼字符串——超省事～
双重 DFS：从网格每个格子出发，一边在 board 上向四周走，一边在 Trie 上同步下探。两边是锁死的：网格走一步，Trie 也必须走一步。
剪枝：如果 Trie 的对应子节点是 nil，说明这条前缀根本不在 words 里，直接 return，一毫秒都不浪费。
收答案 + 防重：每当走到的 Trie 节点有 word != ""，就把这个单词收进 ans，然后立刻 next.word = ""——这一脚超关键，不然同一单词会被网格上不同路径重复收录，坏女人一样！
现场回溯：访问过的格子临时改成 #，四个方向递归完再改回原字符。这叫"原地标记法"，省下一个 visited 二维数组。

对啦对啦，为什么 Trie 节点存 word 而不是老套的 isEnd 布尔？因为 DFS 已经在网格里走了一圈，再花 O(L) 去拼字符串太亏，不如建树的时候顺手把字符串本体挂上去，拿来即用——这就是所谓"算法的仪式感"嘛～

思维边界#

next.word = "" 是去重的灵魂，千万别漏。漏了之后同一个单词会被不同起点/不同路径重复加进答案，结果多出一堆。
# 占位只是"临时告示牌"，回溯时必须恢复成 ch，否则后续的起点 DFS 走到这里会以为是访问过的，静默丢结果。
复杂度看着吓人：O(M·N·4^L)（L 是最长单词长度）。但有了前缀树剪枝，实际 nil 一出现就立刻撤退，性能远比表面数字温柔。
只对小写字母题生效：child[26] 是为 'a'..'z' 量身定制的；题目若包含大写或符号，要换成 map。
本题 words 里单词可能互为前缀（比如 oa、oath），所以即便命中了一个单词也不能提前 return，Trie 下面可能还藏着更长的答案。

搞懂啦就敢说这题简单——本姑娘亲测有效☆

代码#

type TrieNode struct {
    child [26]*TrieNode
    word  string
}

func findWords(board [][]byte, words []string) []string {
    // 构建前缀树
    root := &TrieNode{}
    for _, v := range words {
        node := root
        for _, c := range v {
            index := c - 'a'
            if node.child[index] == nil {
                node.child[index] = &TrieNode{}
            }
            node = node.child[index]
        }
        node.word = v
    }

    ans := []string{}
    var dfs func(i, j int, node *TrieNode)
    dp := [][2]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}
    m := len(board)
    n := len(board[0])
    // 准备深度搜索
    dfs = func(i, j int, node *TrieNode) {
        // 1.先判断边界
        if i < 0 || j < 0 || i >= m || j >= n {
            return
        }

        ch := board[i][j]
        if ch == '#' {
            // 当前节点已访问过
            return
        }
        // 2.剪枝 TrieNode 没有的节点直接返回
        next := node.child[ch-'a']
        if next == nil {
            return
        }
        if next.word != "" {
            ans = append(ans, next.word)
            next.word = ""
        }

        // 3.开始向四周dp
        board[i][j] = '#'
        for _, d := range dp {
            dfs(i+d[0], j+d[1], next)
        }
        board[i][j] = ch // 回溯恢复现场
    }
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            dfs(i, j, root)
        }
    }
    return ans
}