1
package trie
2

3
// TrieNode 表示 Trie 的一个节点
4
type TrieNode struct {
5
    children map[rune]*TrieNode // 子节点映射
6
    isEnd    bool               // 是否为单词终止节点
7
}
8

9
// Trie 前缀树
10
type Trie struct {
11
    root *TrieNode
12
}
13

14
func New() *Trie {
15
    return &Trie{root: &TrieNode{children: make(map[rune]*TrieNode)}}
16
}
17

18
// Insert 插入一个单词，逐字符沿路径走，不存在则创建
19
func (t *Trie) Insert(word string) {
20
    node := t.root
21
    for _, ch := range word {
22
        if node.children[ch] == nil {
23
            node.children[ch] = &TrieNode{children: make(map[rune]*TrieNode)}
24
        }
25
        node = node.children[ch]
26
    }
27
    node.isEnd = true
28
}
29

30
// Search 精确查找，必须完整匹配且终止节点标记为 true
31
func (t *Trie) Search(word string) bool {
32
    node := t.findByPrefix(word)
33
    return node != nil && node.isEnd
34
}
35

36
// StartsWith 前缀搜索：返回所有以 prefix 开头的单词
37
func (t *Trie) StartsWith(prefix string) []string {
38
    node := t.findByPrefix(prefix)
39
    if node == nil {
40
        return nil
41
    }
42
    var results []string
43
    // 从前缀节点出发，深度优先收集所有终止节点
44
    t.collect(node, prefix, &results)
45
    return results
46
}
47

48
// findByPrefix 沿前缀路径定位到目标节点
49
func (t *Trie) findByPrefix(prefix string) *TrieNode {
50
    node := t.root
51
    for _, ch := range prefix {
52
        if node.children[ch] == nil {
53
            return nil
54
        }
55
        node = node.children[ch]
56
    }
57
    return node
58
}
59

60
// collect 深度优先遍历，收集所有终止节点对应的完整单词
61
func (t *Trie) collect(node *TrieNode, path string, results *[]string) {
62
    if node.isEnd {
63
        *results = append(*results, path)
64
    }
65
    for ch, child := range node.children {
66
        t.collect(child, path+string(ch), results)
67
    }
68
}

1
// TrieNode 表示 Trie 的一个节点
2
class TrieNode {
3
  children: Map<string, TrieNode> = new Map();
4
  isEnd: boolean = false;
5
}
6

7
// Trie 前缀树
8
class Trie {
9
  private root: TrieNode = new TrieNode();
10

11
  // 插入一个单词
12
  insert(word: string): void {
13
    let node = this.root;
14
    for (const ch of word) {
15
      if (!node.children.has(ch)) {
16
        node.children.set(ch, new TrieNode());
17
      }
18
      node = node.children.get(ch)!;
19
    }
20
    node.isEnd = true;
21
  }
22

23
  // 精确查找
24
  search(word: string): boolean {
25
    const node = this._findByPrefix(word);
26
    return node !== null && node.isEnd;
27
  }
28

29
  // 前缀搜索：返回所有以 prefix 开头的单词
30
  startsWith(prefix: string): string[] {
31
    const node = this._findByPrefix(prefix);
32
    if (node === null) return [];
33
    const results: string[] = [];
34
    this._collect(node, prefix, results);
35
    return results;
36
  }
37

38
  // 沿前缀路径定位到目标节点
39
  private _findByPrefix(prefix: string): TrieNode | null {
40
    let node = this.root;
41
    for (const ch of prefix) {
42
      const child = node.children.get(ch);
43
      if (child === undefined) return null;
44
      node = child;
45
    }
46
    return node;
47
  }
48

49
  // 深度优先遍历，收集所有终止节点对应的完整单词
50
  private _collect(node: TrieNode, path: string, results: string[]): void {
51
    if (node.isEnd) results.push(path);
52
    for (const [ch, child] of node.children) {
53
      this._collect(child, path + ch, results);
54
    }
55
  }
56
}