211. 添加与搜索单词 - 数据结构设计 Design-add-and-search-words-data-structure
请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。
实现词典类 WordDictionary ：
WordDictionary() 初始化词典对象
void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配
bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回 false 。word 中可能包含一些 '.' ，每个 . 都可以表示任何一个字母。
示例：
输入： ["WordDictionary","addWord","addWord","addWord","search","search","search","search"] [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]] 输出： [null,null,null,null,false,true,true,true] 解释： WordDictionary wordDictionary = new WordDictionary(); wordDictionary.addWord("bad"); wordDictionary.addWord("dad"); wordDictionary.addWord("mad"); wordDictionary.search("pad"); // 返回 False wordDictionary.search("bad"); // 返回 True wordDictionary.search(".ad"); // 返回 True wordDictionary.search("b.."); // 返回 True
提示：
1 <= word.length <= 25addWord中的word由小写英文字母组成search中的word由 '.' 或小写英文字母组成- 最多调用
10^4次addWord和search
代码：
package main import "fmt" type TrieNode struct { children [26]*TrieNode isWord bool } type WordDictionary struct { root *TrieNode } func Constructor() WordDictionary { return WordDictionary{root: &TrieNode{}} } func (this *WordDictionary) AddWord(word string) { node := this.root for _, ch := range word { idx := ch - 'a' if node.children[idx] == nil { node.children[idx] = &TrieNode{} } node = node.children[idx] } node.isWord = true } func (this *WordDictionary) Search(word string) bool { return this.match(this.root, word, 0) } func (this *WordDictionary) match(node *TrieNode, word string, idx int) bool { if node == nil { return false } if idx == len(word) { return node.isWord } ch := word[idx] if ch != '.' { child := node.children[ch-'a'] if child != nil && this.match(child, word, idx+1) { return true } } else { for _, child := range node.children { if child != nil && this.match(child, word, idx+1) { return true } } } return false } func main() { wordDictionary := Constructor() wordDictionary.AddWord("bad") wordDictionary.AddWord("dad") wordDictionary.AddWord("mad") fmt.Println(wordDictionary.Search("pad")) fmt.Println(wordDictionary.Search("bad")) fmt.Println(wordDictionary.Search(".ad")) fmt.Println(wordDictionary.Search("b..")) }
输出：
false
true
true
true
212. 单词搜索 II Word Search ii
给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words， 返回所有二维网格上的单词 。
单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
示例 1：
输入：board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
输出：["eat","oath"]
示例 2：
输入：board = [["a","b"],["c","d"]], words = ["abcb"]
输出：[]
提示：
m == board.length
n == board[i].length
1 <= m, n <= 12
board[i][j] 是一个小写英文字母
1 <= words.length <= 3 * 10^4
1 <= words[i].length <= 10
words[i] 由小写英文字母组成
words 中的所有字符串互不相同
相关题目： 单词搜索 I Word Search i
https://hannyang.blog.csdn.net/article/details/129971403#t0
代码1： 哈希表 + dfs
package main import "fmt" type entry struct { row, col int } func findWords(board [][]byte, words []string) []string { n, m := len(board), len(board[0]) wordIndex := make(map[string]int) for i, word := range words { wordIndex[word] = i } visited := make([][]bool, n) for i := range visited { visited[i] = make([]bool, m) } dirs := []entry{{-1, 0}, {1, 0}, {0, -1}, {0, 1}} var res []string var dfs func(string, int, int) dfs = func(cur string, i, j int) { if idx, ok := wordIndex[cur]; ok { res = append(res, words[idx]) delete(wordIndex, cur) } for _, dir := range dirs { ni, nj := i+dir.row, j+dir.col if ni < 0 || ni >= n || nj < 0 || nj >= m || visited[ni][nj] { continue } visited[ni][nj] = true dfs(cur+string(board[ni][nj]), ni, nj) visited[ni][nj] = false } } for i := 0; i < n; i++ { for j := 0; j < m; j++ { visited[i][j] = true dfs(string(board[i][j]), i, j) visited[i][j] = false } } return res } 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"} fmt.Println(findWords(board, words)) }
代码2： 前缀树 Trie
package main import "fmt" type TrieNode struct { ch byte children [26]*TrieNode word string } type Trie struct { root *TrieNode } func NewTrie() *Trie { return &Trie{root: &TrieNode{}} } func (t *Trie) Insert(word string) { node := t.root for i := 0; i < len(word); i++ { ch := word[i] if idx := ch - 'a'; idx >= 0 && idx < 26 { if node.children[idx] == nil { node.children[idx] = &TrieNode{ch: ch} } node = node.children[idx] } else { return } } node.word = word } func findWords(board [][]byte, words []string) []string { trie := NewTrie() for _, word := range words { trie.Insert(word) } visited := make([][]bool, len(board)) for i := 0; i < len(board); i++ { visited[i] = make([]bool, len(board[0])) } var res []string var dfs func(node *TrieNode, i, j int) dfs = func(node *TrieNode, i, j int) { if node.word != "" { res = append(res, node.word) node.word = "" // 避免重复添加 } if i < 0 || i >= len(board) || j < 0 || j >= len(board[0]) { return } if visited[i][j] || node.children[board[i][j]-'a'] == nil { return } visited[i][j] = true idx := board[i][j] - 'a' child := node.children[idx] dfs(child, i-1, j) dfs(child, i+1, j) dfs(child, i, j-1) dfs(child, i, j+1) visited[i][j] = false } for i := 0; i < len(board); i++ { for j := 0; j < len(board[0]); j++ { dfs(trie.root, i, j) } } return res } 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"} fmt.Println(findWords(board, words)) }
输出：
[oath eat]
