GeezerVison

输入: 
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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

暴力解

困难题，但是暴力解是不难的，就是把单词搜索-79 这题从搜单个词变成搜索多个即可。思路直接看那题的题解吧，这里先放上暴力解的代码：

let dirs = [
  [0, 1],
  [0, -1],
  [-1, 0],
  [1, 0],
]
/**
 * @param {character[][]} board
 * @param {string[]} words
 * @return {string[]}
 */
let findWords = function (board, words) {
  let maxY = board.length
  if (!maxY) return []
  let maxX = board[0].length

  // 记录已访问过的二维下标
  let visited = []
  for (let y = 0; y < maxY; y++) {
    visited[y] = []
  }

  let isValid = (x, y) => {
    return x >= 0 && x < maxX && y >= 0 && y < maxY && !visited[y][x]
  }

  // 返回结果
  let res = []

  let dfs = (x, y, word, index) => {
    let char = board[y][x]
    let targetChar = word[index]
    if (char === targetChar) {
      if (index === word.length - 1) {
        res.push(word)
      } else {
        visited[y][x] = true
        for (let dir of dirs) {
          let [offsetY, offsetX] = dir
          let nextY = y + offsetY
          let nextX = x + offsetX
          if (isValid(nextX, nextY)) {
            dfs(nextX, nextY, word, index + 1)
          }
        }
        visited[y][x] = false
      }
    }
  }

  let find = (word) => {
    for (let y = 0; y < maxY; y++) {
      for (let x = 0; x < maxX; x++) {
        dfs(x, y, word, 0)
      }
    }
  }

  words.forEach(find)

  return res
}

优化

使用 Trie 这种字典树数据结构可以优化这个算法，使得我们的外层双重循环优化到一次。思路是先把题目给出的目标单词 words 都插入到字典树中去，然后遍历的时候只需要去字典树的子节点中寻找当前前缀下有没有下一个字符的子节点即可，这个算法可以优化 10倍左右的时间。

/**
 * Initialize your data structure here.
 */
var Trie = function () {
    this.root = new TrieNode()
}

var TrieNode = function () {
    this.children = new Map()
    this.isEnd = false
}

/**
 * Inserts a word into the trie.
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function (word) {
    let node = this.root

    for (let i = 0; i < word.length; i++) {
        let { children } = node
        let trieNode = children.get(word[i])
        if (!trieNode) {
            trieNode = new TrieNode()
            children.set(word[i], trieNode)
        }
        node = trieNode

        if (i === word.length - 1) {
            node.isEnd = true
            node.word = word
        }
    }
}

let dirs = [
    [0, 1],
    [0, -1],
    [-1, 0],
    [1, 0],
]
/**
 * @param {character[][]} board
 * @param {string[]} words
 * @return {string[]}
 */
let findWords = function (board, words) {
    let maxY = board.length
    if (!maxY) return []
    let maxX = board[0].length

    let rootTrie = new Trie()
    for (let word of words) {
        rootTrie.insert(word)
    }

    // 记录已访问过的二维下标
    let visited = []
    for (let y = 0; y < maxY; y++) {
        visited[y] = []
    }

    let isValid = (x, y) => {
        return x >= 0 && x < maxX && y >= 0 && y < maxY && !visited[y][x]
    }

    // 返回结果
    let res = []

    let dfs = (x, y, trie) => {
        let char = board[y][x]
        let children = trie.children
        let nextTrie = children && children.get(char)
        if (nextTrie) {
            if (nextTrie.word) {
                res.push(nextTrie.word)
                nextTrie.word = null
            }
            visited[y][x] = true
            for (let dir of dirs) {
                let [offsetY, offsetX] = dir
                let nextY = y + offsetY
                let nextX = x + offsetX
                if (isValid(nextX, nextY)) {
                    dfs(nextX, nextY, nextTrie)
                }
            }
            visited[y][x] = false
        }
    }

    for (let y = 0; y < maxY; y++) {
        for (let x = 0; x < maxX; x++) {
            dfs(x, y, rootTrie.root)
        }
    }

    return res
}

Activity

sl1673495
added
递归与回溯
on Jun 24, 2020

daomingQian commented on Oct 27, 2021

daomingQian

on Oct 27, 2021

More actions

不使用前缀树时间超过百分之88

var findWords = function (board, words) {
    const lenbCol = board.length
    const lenbRow = board[0].length
    const lenw = words.length
    const res = []
    const point = [[1,0],[-1,0],[0,1],[0,-1]]

    function dfs(i, j, str, target) {
    if (i < 0 || j < 0 || i >= lenbCol || j >= lenbRow) return false

    let cur = board[i][j] // a
    if (cur === target) {
        return true
    }
        board[i][j] = ''
        let t1 = false,
        t2 = false,
        t3 = false,
        t4 = false
        if (i - 1 >= 0 && cur && target.includes(str + cur)) {
            if (str + cur === target) {
                board[i][j] = cur
                return true
            }
            t1 = dfs(i - 1, j, str + cur, target)
        }
        if (i + 1 < lenbCol && cur && target.includes(str + cur)) {
            if (str + cur === target) {
                board[i][j] = cur
                return true
            }
            t2 = dfs(i + 1, j, str + cur, target)
        }
        if (j - 1 >= 0 && cur && target.includes(str + cur)) {
            if (str + cur === target) {
                board[i][j] = cur
                return true
            }
            t3 = dfs(i, j - 1, str + cur, target)
        }
        if (j + 1 < lenbRow && cur && target.includes(str + cur)) {
            if (str + cur === target) {
                board[i][j] = cur
                return true
            }
            t4 = dfs(i, j + 1, str + cur, target)
        }
        
        board[i][j] = cur

        return t1 || t2 || t3 || t4
    }

    const strB = [...new Set(board.flat())].join('')

    out: for (const str of words) {
        const exist = str.split('').every((ch) => strB.includes(ch))
        if (!exist) continue
        let firstCh = str[0]
        for (let y = 0; y < lenbCol; y++) {
            for (let x = 0; x < lenbRow; x++) {
                const ch = board[y][x]
                if (firstCh === ch && !res.includes(str)) {
                    if (dfs(y, x, '', str)) {
                        res.push(str)
                    }
                    if (res.length >= lenw) break out
                }
            }
        }
    }
    return res
}

Metadata

Assignees

No one assigned

Labels

递归与回溯

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions

You are visitor 01402520 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.