【LeetCode】212 单词搜索 II

优质

小牛编辑

126浏览

2023-12-01

这道题是 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
}