LeetCode 208. 实现 Trie (前缀树) 题解，熟悉Trie结构。

题目

208. 实现 Trie (前缀树)

https://leetcode.cn/problems/implement-trie-prefix-tree/

Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

请你实现 Trie 类：

  • Trie() 初始化前缀树对象。
  • void insert(String word) 向前缀树中插入字符串 word 。
  • boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
  • boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

常规数据结构实现方式

思路

回顾下特里树最简实现及使用场景。

代码

 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

/*
    * 执行用时：
    * 32 ms
    * , 在所有 Java 提交中击败了
    * 88.25%
    * 的用户
    * 内存消耗：
    * 50.7 MB
    * , 在所有 Java 提交中击败了
    * 27.82%
    * 的用户
    * 通过测试用例：
    * 16 / 16
    */
static class Trie {

    /**
        * 当前节点字符表示
        */
    char c;
    /**
        * 下级词字符
        */
    Trie[] children;
    /**
        * 是否为结束点
        */
    boolean stop;

    public Trie() {
        // root
        children = new Trie[26];
    }

    private static boolean strEmpty(String str) {
        if (str == null || str.length() == 0) {
            return true;
        }
        return false;
    }

    public void insert(String word) {
        if (strEmpty(word)) {
            return;
        }
        char[] wordArr = word.toCharArray();
        Trie curr = this;
        for (int i = 0; i < wordArr.length; i++) {
            char c = wordArr[i];
            int charIdx = c - 'a';
            if (curr.children[charIdx] == null) {
                Trie node = new Trie();
                node.c = c;
                curr.children[charIdx] = node;
            }
            if (i == wordArr.length - 1) {
                curr.children[charIdx].stop = true;
            }
            curr = curr.children[charIdx];
        }
    }

    public boolean search(String word) {
        if (strEmpty(word)) {
            return false;
        }
        Trie lastNode = searchPrefixLastNode(word);
        return lastNode != null && lastNode.stop;
    }

    public boolean startsWith(String prefix) {
        if (strEmpty(prefix)) {
            return false;
        }
        Trie lastNode = searchPrefixLastNode(prefix);
        return lastNode != null;
    }

    private Trie searchPrefixLastNode(String prefix) {
        char[] wordArr = prefix.toCharArray();
        Trie curr = this;
        for (int i = 0; i < wordArr.length; i++) {
            char c = wordArr[i];
            int charIdx = c - 'a';
            if (curr == null || curr.children == null || curr.children[charIdx] == null) {
                return null;
            }
            if (wordArr[i] != curr.children[charIdx].c) {
                return null;
            }
            curr = curr.children[charIdx];
        }
        return curr;
    }

}

复杂度分析

时间

Trie类构造器中每次创建一个固定26长度的数组，时间复杂度O(1)。

读写操作复杂度取决于单词长度，复杂度O(word.len)。

空间

空间复杂度近似O(n)，n为所有单词字符数和。

Ref