📝【LeetCode】212 单词搜索 II
这道题是 LeetCode 212 题，是 79 题的升级版。
给定一个二维网格和包含多个单词的字典，找出所有同时在二维网格和字典中出现的单词。
解法一：回溯
直接使用 79 题的代码，依次查找每个单词是否在 board 中有一条对应的路径。
时间复杂度：$(n×4^L)$，$n$ 为单词个数，$L$ 为单词的最大长度
- 搜索每个单词的时间复杂度相当于搜索树的节点数。搜索最大深度为 $L$，$L$ 为当前单词的长度；每次搜索可能向 4 个方向分叉。故搜索树是一颗最大深度为 $L$ 的 4 叉树，其节点总数为 $O(4^L)$
- 对于每个单词，需要重新构造搜索树
用时 252ms。
var res []string
func findWords(board [][]byte, words []string) []string {
if len(words) == 0 || len(board) == 0 {
return nil
}
res = nil
for _, w := range words {
if exist(board, w) {
res = append(res, w)
}
}
return res
}
func exist(board [][]byte, word string) bool {
if len(word) == 0 || len(board) == 0 {
return false
}
for i := 0; i < len(board); i++ { // 从每个位置开始找
for j := 0; j < len(board[0]); j++ {
if dfs(board, i, j, word) {
return true
}
}
}
return false
}
// row、col 表示当前搜索的起始位置，board[i][j]=='$' 表示 board[i][j] 已经被搜索
func dfs(board [][]byte, row, col int, word string) bool {
if board[row][col] != word[0] {
return false
}
if len(word) == 1 {
return true
}
board[row][col] = '$'
found := false
if row > 0 && board[row-1][col] != '$' {
found = found || dfs(board, row-1, col, word[1:])
}
if col < len(board[0])-1 && board[row][col+1] != '$' {
found = found || dfs(board, row, col+1, word[1:])
}
if row < len(board)-1 && board[row+1][col] != '$' {
found = found || dfs(board, row+1, col, word[1:])
}
if col > 0 && board[row][col-1] != '$' {
found = found || dfs(board, row, col-1, word[1:])
}
board[row][col] = word[0]
return found
}
解法二：回溯 + 前缀树
解法一中，每个单词是独立查找，对于有相同前缀的多个单词，这些前缀的路径会被重复的搜索。比如 food 和 foot，查找 food 的时候可能就已经搜到 foo 的路径了，foot 可以直接从 foo 的路径继续往下搜索。
可以使用前缀树优化，前缀树可以直接使用 208 题的代码。这相当于批量地查找多个单词，相同的前缀只会查找一次，节省了时间。
前缀树的性质是：若前缀树的某个节点 isLast==true，则前缀树根节点到这个节点的路径构成了一个单词。那么解法二的思路可以描述为：“依次查找前缀树中从根节点到 isLast==true 的节点的每条路径，是否在 board 中有一条同样的路径”。
假设有这样一个问题：分别从二叉树 A 和 B 的根节点开始，搜索两个树是否有相同的路径。那么肯定是两颗树同步搜索：如果 rootA.val == rootB.val，则树 A 进入左子树，树 B 也进入左子树；否则，回退到上一层，换一棵子树继续搜索。
同理，如果我们将递归搜索 board 的过程想象成一棵搜索树，那么前缀树和 board 的搜索树也可以同步地更新：设前缀树的当前节点为 A，搜索树的当前节点为 B，则如果 A 某个子节点的值等于 B 的值，那么令 A 为该子节点，B 进入下一层开始搜索。这里可以看代码。
时间复杂度：$(4^L)$，$L$ 为单词的最大长度。可以这样理解：最差情况下，每个单词都没有相同的前缀，此时利用前缀树查找也等同于依次查找每个单词，这种情况下时间复杂度同解法一 $(n×4^L)$；而最优情况下，每个单词都相同，这时利用前缀树查找相当于只查找一个单词，时间复杂度为 $(4^L)$。故平均时间复杂度为 $(4^L)$。
用时 40 ms，时间更短。
func findWords(board [][]byte, words []string) []string {
if len(words) == 0 || len(board) == 0 {
return nil
}
resMap := map[string]int{}
trie := NewTrie()
for _, w := range words {
trie.Insert(w)
}
for i := 0; i < len(board); i++ { // 从每个位置开始找
for j := 0; j < len(board[0]); j++ {
dfs(trie, board, i, j, "", resMap)
}
}
res := []string{}
for key := range resMap {
res = append(res, key)
}
return res
}
// 在以 root 为根节点的前缀树中，搜索 board 是否有匹配的前缀
// root 本身不包含字符，其子节点才包含字符
// row、col 表示当前搜索的起始位置，board[i][j]=='$' 表示 board[i][j] 已经被搜索
func dfs(root *Trie, board [][]byte, row, col int, prefix string, resMap map[string]int) {
for i, node := range root.children {
if node != nil && board[row][col] == byte(i)+'a' { // 如果某个子节点和 board 起始点匹配
nextPrefix := prefix + string(byte(i)+'a') // 将子节点的值加入到前缀串中
if node.isLast { // 如果子节点表示一个单词，则将其加入到结果中
resMap[nextPrefix] = 1
}
board[row][col] = '$'
if row > 0 && board[row-1][col] != '$' {
dfs(node, board, row-1, col, nextPrefix, resMap)
}
if col < len(board[0])-1 && board[row][col+1] != '$' {
dfs(node, board, row, col+1, nextPrefix, resMap)
}
if row < len(board)-1 && board[row+1][col] != '$' {
dfs(node, board, row+1, col, nextPrefix, resMap)
}
if col > 0 && board[row][col-1] != '$' {
dfs(node, board, row, col-1, nextPrefix, resMap)
}
board[row][col] = byte(i) + 'a'
}
}
}
type Trie struct {
children []*Trie
isLast bool // 是否某个单词以当前节点为最后一个节点。isLast == true 不代表当前节点是叶节点
}
func NewTrie() *Trie {
return &Trie{
children: make([]*Trie, 26),
}
}
func (this *Trie) Insert(word string) {
cur := this
for i := 0; i < len(word); i++ {
char := word[i]
if cur.children[char-'a'] == nil {
cur.children[char-'a'] = NewTrie()
}
cur = cur.children[char-'a']
}
cur.isLast = true
}
优化解法二
解法二已经包含的优化：board[i][j]=='$' 表示 board[i][j] 已经被搜索，这样不需要一个 visit[m][n] 数组。
解法二的搜索过程中，需要使用一个 HashMap 去掉重复查找到的单词。可以在每次找到某个单词后，令 node.isLast = false，这相当于从前缀树中删除该单词，就不需要额外的 HashMap 了。
if node.isLast { // 如果子节点表示一个单词，则将其加入到结果中
- resMap[nextPrefix] = 1
+ res = append(res, nextPrefix)
+ node.isLast = false
}
此外，解法二使用的前缀树每个节点并不保存单词，而是通过根节点到该节点的路径来表示一个单词。因此搜索过程中需要维护一个字符串 prefix，表示当前搜索的前缀。
其实可以直接将完整单词保存在前缀树的 node 里，就不需要 prefix 了，能够避免频繁地构建字符串，在字典里包含特别长的单词的时候可以提升运行速度。
优化后的代码：
var res []string
func findWords(board [][]byte, words []string) []string {
if len(words) == 0 || len(board) == 0 {
return nil
}
res = nil
trie := NewTrie()
for _, w := range words {
trie.Insert(w)
}
for i := 0; i < len(board); i++ { // 从每个位置开始找
for j := 0; j < len(board[0]); j++ {
dfs(trie, board, i, j)
}
}
return res
}
// 在以 root 为根节点的前缀树中，搜索 board 是否有匹配的前缀
// root 本身不包含字符，其子节点才包含字符
// row、col 表示当前搜索的起始位置，board[i][j]=='$' 表示 board[i][j] 已经被搜索
func dfs(root *Trie, board [][]byte, row, col int) {
for i, node := range root.children {
if node != nil && board[row][col] == byte(i)+'a' { // 如果某个子节点和 board 起始点匹配
if node.word != "" { // 如果子节点表示一个单词，则将其加入到结果中
res = append(res, node.word)
node.word = ""
}
board[row][col] = '$'
if row > 0 && board[row-1][col] != '$' {
dfs(node, board, row-1, col)
}
if col < len(board[0])-1 && board[row][col+1] != '$' {
dfs(node, board, row, col+1)
}
if row < len(board)-1 && board[row+1][col] != '$' {
dfs(node, board, row+1, col)
}
if col > 0 && board[row][col-1] != '$' {
dfs(node, board, row, col-1)
}
board[row][col] = byte(i) + 'a'
}
}
}
type Trie struct {
children []*Trie
word string // 如果当前节点为最后一个节点，保存其表示的单词
}
func NewTrie() *Trie {
return &Trie{
children: make([]*Trie, 26),
}
}
func (this *Trie) Insert(word string) {
cur := this
for i := 0; i < len(word); i++ {
char := word[i]
if cur.children[char-'a'] == nil {
cur.children[char-'a'] = NewTrie()
}
cur = cur.children[char-'a']
}
cur.word = word
}
结语
本文发表在我的博客 https://imageslr.com/。我也会分享更多的题解，一起交流，共同进步！
- 版权声明：本文采用知识共享 3.0 许可证 (保持署名-自由转载-非商用-非衍生)
- 发表于 2020-02-01