题目：
难度：Hard
相关话题：字典树、回溯算法
给定一个二维网格board 和一个字典中的单词列表 words ，找出所有同时在二维网格和字典中出现的单词。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
示例:
输入:
words = ["oath","pea","eat","rain"] and board=
[
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
]
输出:["eat","oath"]
说明: 你可以假设所有输入都由小写字母 a-z 组成。
提示:
思路：
先对words构建Tire树，接着对board上每一个点作为起点，dfs遍历查找是否存在tire.word，tire.word意味着单词背查找到， 如果存在，将tire.word添加到结果中并且设置为null(避免重复查找)。
/**
* @来源： Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍：一个致力于帮助开发者用代码改变世界为使命的平台，每天都可以在这里找到技术世界的头条内容
* @param {character[][]} board
* @param {string[]} words
* @return {string[]}
*/
function findWords(board, words) {
let tire={}
for(let i=0;i<words.length;i++){
let t=tire
for(let j=0;j<words[i].length;j++){
let l=words[i][j]
if(t[l]==null)t[l]={}
if(j===words[i].length-1){
t[l].word=words[i]
}
t=t[l]
}
}
let res=[]
let m=board.length,n=board[0].length
let moves=[[1,0],[-1,0],[0,1],[0,-1]]
let used=Array(m).fill().map(()=>Array(n).fill(0)),uniq=0
for (let i = 0; i < board.length; i++) {
for (let j = 0; j < board[0].length; j++) {
if(tire[board[i][j]]==null)continue
uniq++
dfs([i,j],tire[board[i][j]])
}
}
return res
function dfs([x,y],tire){
if(tire.word){
res.push(tire.word)
tire.word=null
}
used[x][y]=uniq
for(let [dX,dY] of moves){
let nX=x+dX,nY=y+dY
if(nX<0 || nY<0 || nX>=m || nY>=n)continue
if(used[nX][nY]===uniq)continue
if(tire[board[nX][nY]]==null)continue
dfs([nX,nY],tire[board[nX][nY]])
}
used[x][y]=uniq-1
}
};
扩展阅读：