LeetCode 212. 单词搜索 II

[Chocolate1999]

仰望星空的人，不应该被嘲笑

题目描述

给定一个二维网格 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 组成。

提示:

你需要优化回溯算法以通过更大数据量的测试。你能否早点停止回溯？
如果当前单词不存在于所有单词的前缀中，则可以立即停止回溯。什么样的数据结构可以有效地执行这样的操作？散列表是否可行？为什么？ 前缀树如何？如果你想学习如何实现一个基本的前缀树，请先查看这个问题： 实现Trie（前缀树）。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-search-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

参考力扣官网分析：实现 Trie (前缀树)

• 判断是否找到了，通过传递节点的END来判断

• 判断是否重复访问，通过动态更改走过的网格点来判断，就不需要再定义一个vis数组了

参考大佬：秦时明月字典树建树解法（二）

var findWords = function(grid, words) {
  // 存放最终结果集
  let res = []
  // 字典树节点
  class TrieNode {
    constructor(){
      this.end = false
      this.child = {}
    }
  }
  // 最终形成的字典树根节点
  let root = null
  let Trie = function(){
    root = new TrieNode()
  }
  // 建立字典树
  Trie.prototype.insert = (word) => {
    let cur = root
    for(let i=0;i<word.length;i++){
      if(!cur.child[word[i]]){
        cur.child[word[i]] = new TrieNode()
      }
      cur = cur.child[word[i]]
    }
    cur.end = true
  }
  // 创建根节点
  let trie = new Trie()
  // 进行建树操作
  for(let i=0;i<words.length;i++){
    trie.insert(words[i])
  }
  let dfs = (x,y,t,cur) => {
    if(cur.end){
      res.push(t)
      cur.end = false // 避免重复计算
    }
    // 剪枝条件：1.边界处理 2.下一步是否可走 3.下一步字典树是否可走
    if(x<0 || x>=grid.length || y<0 || y>=grid[0].length || grid[x][y] == '#' || !cur.child[grid[x][y]]) return
    let tmp = grid[x][y]
    grid[x][y] = '#'  // 走
    cur = cur.child[tmp]
    dfs(x+1,y,t+tmp,cur)  // 上下左右四个方向遍历
    dfs(x,y+1,t+tmp,cur)
    dfs(x-1,y,t+tmp,cur)
    dfs(x,y-1,t+tmp,cur)
    grid[x][y] = tmp // 回溯（还原）
  }
  // 对单词表进行全局搜索
  for(let i=0;i<grid.length;i++){
    for(let j=0;j<grid[0].length;j++){
      dfs(i,j,'',root)
    }
  }
  return res
};

附上完整字典树（前缀树）模板，日后可用~

在 Trie 树中查找键

每个键在 trie 中表示为从根到内部节点或叶的路径。我们用第一个键字符从根开始，。检查当前节点中与键字符对应的链接。有两种情况：

• 存在链接。我们移动到该链接后面路径中的下一个节点，并继续搜索下一个键字符。
• 不存在链接。若已无键字符，且当前结点标记为 isEnd，则返回 true。否则有两种可能，均返回 false :
  还有键字符剩余，但无法跟随 Trie 树的键路径，找不到键。
  没有键字符剩余，但当前结点没有标记为 isEnd。也就是说，待查找键只是Trie树中另一个键的前缀。

查找 Trie 树中的键前缀

该方法与在 Trie 树中搜索键时使用的方法非常相似。我们从根遍历 Trie 树，直到键前缀中没有字符，或者无法用当前的键字符继续 Trie 中的路径。与上面提到的“搜索键”算法唯一的区别是，到达键前缀的末尾时，总是返回 true。我们不需要考虑当前 Trie 节点是否用 “isend” 标记，因为我们搜索的是键的前缀，而不是整个键。

作者：LeetCode
链接：https://leetcode-cn.com/problems/implement-trie-prefix-tree/solution/shi-xian-trie-qian-zhui-shu-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

var findWords = function(grid, words) {
  // 存放最终结果集
  let res = []
  // 字典树节点
  class TrieNode {
    constructor(){
      this.end = false
      this.child = {}
    }
  }
  // 最终形成的字典树根节点
  let root = null
  let Trie = function(){
    root = new TrieNode()
  }
  // 建立字典树
  Trie.prototype.insert = (word) => {
    let cur = root
    for(let i=0;i<word.length;i++){
      if(!cur.child[word[i]]){
        cur.child[word[i]] = new TrieNode()
      }
      cur = cur.child[word[i]]
    }
    cur.end = true
  }
  // 在 Trie 树中查找键
  let searchPrefix = (word) => {
    let cur = root
    for(let i=0;i<word.length;i++){
      if(cur.child[word[i]]){
        cur = cur.child[word[i]]
      }else{
        return null
      }
    }
    return cur
  }
  Trie.prototype.search = (word) => {
    let cur = searchPrefix(word)
    return cur !== null && cur.end
  }
  // 查找 Trie 树中的键前缀
  Trie.prototype.startsWith = (pre) => {
    return searchPrefix(pre) != null
  }
  // 创建根节点
  let trie = new Trie()
  // 进行建树操作
  for(let i=0;i<words.length;i++){
    trie.insert(words[i])
  }
  let dfs = (x,y,t,cur) => {
    if(cur.end){
      res.push(t)
      cur.end = false // 避免重复计算
    }
    // 剪枝条件：1.边界处理 2.下一步是否可走 3.下一步字典树是否可走
    if(x<0 || x>=grid.length || y<0 || y>=grid[0].length || grid[x][y] == '#' || !cur.child[grid[x][y]]) return
    let tmp = grid[x][y]
    grid[x][y] = '#'  // 走
    cur = cur.child[tmp]
    dfs(x+1,y,t+tmp,cur)  // 上下左右四个方向遍历
    dfs(x,y+1,t+tmp,cur)
    dfs(x-1,y,t+tmp,cur)
    dfs(x,y-1,t+tmp,cur)
    grid[x][y] = tmp // 回溯（还原）
  }
  // 对单词表进行全局搜索
  for(let i=0;i<grid.length;i++){
    for(let j=0;j<grid[0].length;j++){
      dfs(i,j,'',root)
    }
  }
  return res
};

最后

文章产出不易，还望各位小伙伴们支持一波！

往期精选：

小狮子前端の笔记仓库

访问超逸の博客，方便小伙伴阅读玩耍~

学如逆水行舟，不进则退