添加与搜索单词

代码 · 当前高亮行随帧切换

1type Node struct {
2    children [26]*Node
3    isEnd    bool
4}
5 
6func (d *WordDictionary) AddWord(word string) {
7    node := d.root
8    for _, c := range word {
9        i := c - 'a'
10        if node.children[i] == nil {
11            node.children[i] = &Node{}
12        }
13        node = node.children[i]
14    }
15    node.isEnd = true
16}
17 
18func (d *WordDictionary) Search(word string) bool {
19    return dfs(d.root, word, 0)
20}
21 
22func dfs(node *Node, word string, i int) bool {
23    if i == len(word) {
24        return node.isEnd
25    }
26    c := word[i]
27    if c == '.' {
28        for _, child := range node.children {
29            if child != nil && dfs(child, word, i+1) {
30                return true
31            }
32        }
33        return false
34    }
35    next := node.children[c-'a']
36    if next == nil {
37        return false
38    }
39    return dfs(next, word, i+1)
40}