leetcode 212题 单词搜索 II
给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words，找出所有同时在二维网格和字典中出现的单词。
单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
示例 1：
输入：board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
输出：["eat","oath"]
示例 2：
输入：board = [["a","b"],["c","d"]], words = ["abcb"]
输出：[]
思路
前缀树 + 剪枝 + 回溯
代码
var findWords = function(board, words) {
const table = {} // 前缀表
const result = [] // 结果集数组
/** 单词表 → 哈希表 → 前缀树 **/
for (const word of words) {// 遍历单词表，用哈希表组装前缀树
for(var i = 0, _table = table, prev; i < word.length; i++) {
const ch = word[i];
if (!_table[ch]) {
_table[ch] = Object.create(null) // 创建一个不含_proto_的纯净对象作节点，比{}提升性能
_table[ch].len = 0 // 初始节点长度设为`0`，后面会`+1`
}
prev = _table // 存前缀树上一级节点
_table = _table[ch] // 移到当前节点
_table.prev = prev // 当前节点的`prev`属性，指向上一级节点
_table.len++ // 单词共享前缀的情况，节点长度`+1`。在剪枝时，通过prev向上查找，直到len != 1，删除单词在前缀树的独占部分
}
_table.word = word // 当前单词的前缀树最后一个字母，添加单词结尾标记，内容就是 单词本身
}
/** 剪枝 **/
const splice = (table, prev) => {// 找到一个单词，就删掉 这个单词所在的前缀树，但不能影响其他单词，所以只删节点长度1（该单词独占）
while(table.len === 1) prev = table, table = table.prev // 从当前节点层层向上，直到节点长度不为1，存在分支
for(var key in prev) delete prev[key]// prev暂存最后一个节点长度为1的节点，把p从前缀树剪掉
}
/** 二维网络 → 递归 → 找前缀树中的单词 **/
const recursion = (i, j, table) => { // 递归
var cell = board[i] && board[i][j] // 暂存单元格字母
if (cell === false || table[cell] === undefined) return // 字母不存在（逾界） 或 字母不再前缀表
table = table[cell] // 字母在前缀表，向下找后面的节点
if (table.word) { // 该字母是不是某个单词的结尾（组装前缀表时，把单词结尾标记 设为 单词本身）
result.push(table.word) // 将单词放入结果集
table.word = '' // 当单词结尾标记置空，避免这个单词被重复找到
splice(table) // 剪枝，传入前缀树当前节点
}
board[i][j] = '' // 当前格子找过了，值清空，继续递归不再找
recursion(i - 1, j, table), recursion(i + 1, j, table), recursion(i, j - 1, table), recursion(i, j + 1, table) // 从当前格子开始，向四周继续递归
board[i][j] = cell // 回溯时，将当前格子值复原
}
for (let i = board.length; i--;) {// 遍历二维网格，将每个格子作为开始前缀，在前缀树找完整单词
for (let j = board[0].length; j--;) {
recursion(i, j, table)
}
}
return result
};
复杂度分析
- 时间复杂度：O(N^2)
- 空间复杂度：O(N)