Open sl1673495 opened 4 years ago
不使用前缀树 时间超过百分之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
}
给定一个二维网格 board 和一个字典中的单词列表 words,找出所有同时在二维网格和字典中出现的单词。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
示例:
提示:
你需要优化回溯算法以通过更大数据量的测试。你能否早点停止回溯? 如果当前单词不存在于所有单词的前缀中,则可以立即停止回溯。什么样的数据结构可以有效地执行这样的操作?散列表是否可行?为什么? 前缀树如何?如果你想学习如何实现一个基本的前缀树,请先查看这个问题: 实现Trie(前缀树)。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/word-search-ii 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
暴力解
困难题,但是暴力解是不难的,就是把单词搜索-79 这题从搜单个词变成搜索多个即可。思路直接看那题的题解吧,这里先放上暴力解的代码:
优化
使用
Trie
这种字典树数据结构可以优化这个算法,使得我们的外层双重循环优化到一次。思路是先把题目给出的目标单词words
都插入到字典树中去,然后遍历的时候只需要去字典树的子节点中寻找当前前缀下有没有下一个字符的子节点即可,这个算法可以优化 10倍左右的时间。