单词搜索 II。给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words，找出所有同时在二维网格和字典中出现的单词。单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。力扣212。
前缀树。
代码用golang编写。代码如下：
package main
import "fmt"
func main() {
board := [][]byte{{'o', 'a', 'a', 'n'}, {'e', 't', 'a', 'e'}, {'i', 'h', 'k', 'r'}, {'i', 'f', 'l', 'v'}}
words := []string{"oath", "pea", "eat", "rain"}
ret := findWords(board, words)
fmt.Println(ret)
}
type TrieNode struct {
nexts []*TrieNode
pass int
end bool
}
func NewTrieNode() *TrieNode {
ans := &TrieNode{}
ans.nexts = make([]*TrieNode, 26)
ans.pass = 0
ans.end = false
return ans
}
func fillWord(head *TrieNode, word string) {
head.pass++
chs := []byte(word)
index := 0
node := head
for i := 0; i < len(chs); i++ {
index = int(chs[i] - 'a')
if node.nexts[index] == nil {
node.nexts[index] = NewTrieNode()
}
node = node.nexts[index]
node.pass++
}
node.end = true
}
func generatePath(path []byte) string { //LinkedList<Character>
str := make([]byte, len(path))
index := 0
for _, cha := range path {
str[index] = cha
index++
}
return string(str)
}
func findWords(board [][]byte, words []string) []string {
head := NewTrieNode() // 前缀树最顶端的头
set := make(map[string]struct{})
for _, word := range words {
if _, ok := set[word]; !ok {
fillWord(head, word)
set[word] = struct{}{}
}
}
// 答案
ans := make([]string, 0)
// 沿途走过的字符，收集起来，存在path里
path := make([]byte, 0)
for row := 0; row < len(board); row++ {
for col := 0; col < len(board[0]); col++ {
// 枚举在board中的所有位置
// 每一个位置出发的情况下，答案都收集
process(board, row, col, &path, head, &ans)
}
}
return ans
}
// 从board[row][col]位置的字符出发，
// 之前的路径上，走过的字符，记录在path里
// cur还没有登上，有待检查能不能登上去的前缀树的节点
// 如果找到words中的某个str，就记录在 res里
// 返回值，从row,col 出发，一共找到了多少个str
func process(board [][]byte, row int, col int, path *[]byte, cur *TrieNode, res *[]string) int {
cha := board[row][col]
if cha == 0 { // 这个row col位置是之前走过的位置
return 0
}
// (row,col) 不是回头路 cha 有效
index := cha - 'a'
// 如果没路，或者这条路上最终的字符串之前加入过结果里
if cur.nexts[index] == nil || cur.nexts[index].pass == 0 {
return 0
}
// 没有走回头路且能登上去
cur = cur.nexts[index]
*path = append(*path, cha) // 当前位置的字符加到路径里去
fix := 0 // 从row和col位置出发，后续一共搞定了多少答案
// 当我来到row col位置，如果决定不往后走了。是不是已经搞定了某个字符串了
if cur.end {
*res = append(*res, generatePath(*path))
cur.end = false
fix++
}
// 往上、下、左、右，四个方向尝试
board[row][col] = 0
if row > 0 {
fix += process(board, row-1, col, path, cur, res)
}
if row < len(board)-1 {
fix += process(board, row+1, col, path, cur, res)
}
if col > 0 {
fix += process(board, row, col-1, path, cur, res)
}
if col < len(board[0])-1 {
fix += process(board, row, col+1, path, cur, res)
}
board[row][col] = cha
//path.pollLast()
*path = (*path)[0 : len(*path)-1]
cur.pass -= fix
return fix
}执行结果如下：
