题目地址(212. 单词搜索 II)
https://leetcode-cn.com/problems/word-search-ii/description/
题目描述
给定一个二维网格 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(前缀树)。
思路
我们需要对矩阵中每一项都进行深度优先遍历(DFS)。 递归的终点是
-
- 超出边界
-
- 递归路径上组成的单词不在 words 的前缀。
比如题目示例:words = ["oath","pea","eat","rain"],那么对于 oa,oat 满足条件,因为他们都是 oath 的前缀,但是 oaa 就不满足条件。
为了防止环的出现,我们需要记录访问过的节点。而返回结果是需要去重的。出于简单考虑,我们使用集合(set),最后返回的时候重新转化为 list。
刚才我提到了一个关键词“前缀”,我们考虑使用前缀树来优化。使得复杂度降低为$O(h)$, 其中 h 是前缀树深度,也就是最长的字符串长度。
关键点
- 前缀树(也叫字典树),英文名 Trie(读作 tree 或者 try)
- DFS
- hashmap 结合 dfs 记录访问过的元素的时候,注意结束之后需要将 hashmap 的值重置。(下方代码的
del seen[(i, j)]
)
代码
- 语言支持:Python3
Python3 Code:
关于 Trie 的代码:
class Trie: def __init__(self): """ Initialize your data structure here. """ self.Trie = {} def insert(self, word): """ Inserts a word into the trie. :type word: str :rtype: void """ curr = self.Trie for w in word: if w not in curr: curr[w] = {} curr = curr[w] curr['#'] = 1 def startsWith(self, prefix): """ Returns if there is any word in the trie that starts with the given prefix. :type prefix: str :rtype: bool """ curr = self.Trie for w in prefix: if w not in curr: return False curr = curr[w] return True
主逻辑代码:
class Solution: def findWords(self, board: List[List[str]], words: List[str]) -> List[str]: m = len(board) if m == 0: return [] n = len(board[0]) trie = Trie() seen = None res = set() for word in words: trie.insert(word) def dfs(s, i, j): if (i, j) in seen or i < 0 or i >= m or j < 0 or j >= n or not trie.startsWith(s): return s += board[i][j] seen[(i, j)] = True if s in words: res.add(s) dfs(s, i + 1, j) dfs(s, i - 1, j) dfs(s, i, j + 1) dfs(s, i, j - 1) del seen[(i, j)] for i in range(m): for j in range(n): seen = dict() dfs("", i, j) return list(res)
相关题目
- 208.implement-trie-prefix-tree
- 211.add-and-search-word-data-structure-design
题目地址(211. 添加与搜索单词 - 数据结构设计) https://leetcode-cn.com/problems/add-and-search-word-data-structure-design/description/ 题目描述 设计一个支持以下两种操作的数据结构: void addWord(word) bool search(word) sea…
LeetCode题解45.跳跃游戏 II给定一个非负整数数组,你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。示例:输入: [2,3,1,1,4]输出: 2解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。说明:假设你总是可以到达数…
LeetCode题解140. 单词拆分 II批注: 由于"可以重复使用字典中的单词", 因此稍微难一点定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,在字符串中增加空格来构建一个句子,使得句子中所有的单词都在词典中。返回所有这些可能的句子。说明:分隔时可以重复使用字典中的单词。你可以假设字典中没有重复的单词。示例 1:输入:s = "catsanddog"wordDict = […
LeetCode题解142. 环形链表 II为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。说明:不允许修改给定的链表。 示例 1:输入:head = [3,2,0,-4], pos = 1输出:tail connects to node index 1解释:链表中有一个环,其尾部连接到第二个节点。示例 2…
LeetCode题解213. 打家劫舍 II你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,能够偷窃到的最高金额。示例 1:输入: [2,3…