1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

// @Title: 单词搜索 II (Word Search II)
// @Author: 15816537946@163.com
// @Date: 2019-09-05 15:50:05
// @Runtime: 28 ms
// @Memory: 16.6 MB
/*
 * @lc app=leetcode.cn id=212 lang=golang
 *
 * [212] 单词搜索 II
 *
 * https://leetcode-cn.com/problems/word-search-ii/description/
 *
 * algorithms
 * Hard (36.20%)
 * Likes:    55
 * Dislikes: 0
 * Total Accepted:    4.4K
 * Total Submissions: 12.2K
 * Testcase Example:  '[["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]]\n["oath","pea","eat","rain"]'
 *
 * 给定一个二维网格 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（前缀树）。
 *
 *
 */

type Trie struct {
	children [26]*Trie
	val      string // record word
}

func buildTire(words []string) *Trie {
	newRoot := new(Trie)

	for _, word := range words {
		var idx int
		root := newRoot
		for _, v := range word {
			idx = int(v - 'a')

			// insert
			if root.children[idx] == nil {
				root.children[idx] = &Trie{}
			}
			root = root.children[idx]
		}
		root.val = word
	}
	return newRoot
}

func findWords(board [][]byte, words []string) []string {
	res := make([]string, 0)
	// res := []string{}
	tireRoot := buildTire(words)
	for i := range board {
		for j := range board[0] {
			dfs(board, i, j, tireRoot, &res)
		}
	}

	return res
}

func dfs(board [][]byte, i, j int, p *Trie, res *[]string) {
	char := board[i][j]
	// 边界条件
	idx := int(char - 'a')
	if char == '#' || p.children[idx] == nil {
		return
	}

	p = p.children[idx]
	if p.val != "" {
		*res = append(*res, p.val)
		p.val = ""
	}

	// 避免重复搜索
	board[i][j] = '#'

	// 回溯
	if i > 0 {
		dfs(board, i-1, j, p, res)
	}
	if j > 0 {
		dfs(board, i, j-1, p, res)
	}
	if i < len(board)-1 {
		dfs(board, i+1, j, p, res)
	}
	if j < len(board[0])-1 {
		dfs(board, i, j+1, p, res)
	}

	board[i][j] = char // ???
}