算法基础-前缀树

 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

package main

type TrieNode struct {
	isWord   bool
	children []*TrieNode
}

func NewTrieNode() *TrieNode {
	return &TrieNode{
		isWord:   false,
		children: make([]*TrieNode, 26),
	}
}

type Trie struct {
	root *TrieNode
}

func NewTrie() Trie {
	return Trie{NewTrieNode()}
}

func (t *Trie) Insert(word string) {
	node := t.root
	for i := range word {
		idx := int(word[i] - 'a')
		if node.children[idx] == nil {
			node.children[idx] = NewTrieNode()
		}
		node = node.children[idx]
	}
	node.isWord = true
}

func (t *Trie) Search(word string) bool {
	node := t.GetNode(word)
	if node == nil || !node.isWord {
		return false
	}
	return true
}

func (t *Trie) StartsWith(prefix string) bool {
	return t.GetNode(prefix) != nil
}

func (t *Trie) GetNode(word string) *TrieNode {
	node := t.root
	for i := range word {
		idx := int(word[i] - 'a')
		child := node.children[idx]
		if child == nil {
			return nil
		}
		node = child
	}
	return node
}

func (t *Trie) Scan(prefix string) []string {
	node := t.GetNode(prefix)
	res := make([]string, 0)
	if node == nil {
		return res
	}
	var dfs func(node *TrieNode, path []byte)
	dfs = func(node *TrieNode, path []byte) {
		if node == nil {
			return
		}
		if node.isWord {
			res = append(res, prefix+string(path))
		}
		for i := 0; i < 26; i++ {
			child := node.children[i]
			if child != nil {
				path = append(path, byte(i+'a'))
				dfs(child, path)
				path = path[:len(path)-1]
			}
		}
	}
	dfs(node, []byte{})
	return res
}