LeetCode: 208. Implement Trie (Prefix Tree)

友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

208. Implement Trie (Prefix Tree)

LeetCode - Implement Trie (Prefix Tree)

没想到 Trie Tree 实现起来一点也不复杂！

思考题：如何实现一个工业级的 Trie Tree？

参考资料

Implement a trie with insert, search, and startsWith methods.

Example:

Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // returns true
trie.search("app");     // returns false
trie.startsWith("app"); // returns true
trie.insert("app");
trie.search("app");     // returns true

Note:

You may assume that all inputs are consist of lowercase letters a-z.
All inputs are guaranteed to be non-empty strings.

 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
/**
 * Runtime: 69 ms, faster than 11.59% of Java online submissions for Implement Trie (Prefix Tree).
 *
 * Memory Usage: 62.6 MB, less than 5.77% of Java online submissions for Implement Trie (Prefix Tree).
 */
class Trie {
    private int ALPHABET_SIZE = 26;

    class TrieNode {
        private TrieNode[] alphabet;
        private boolean isEnd;

        public TrieNode() {
            this.alphabet = new TrieNode[ALPHABET_SIZE];
            Arrays.fill(this.alphabet, null);
            this.isEnd = false;
        }
    }

    private TrieNode[] root;

    /**
     * Initialize your data structure here.
     */
    public Trie() {
        this.root = new TrieNode[ALPHABET_SIZE];
        Arrays.fill(this.root, null);
    }

    /**
     * Inserts a word into the trie.
     */
    public void insert(String word) {
        char[] chars = word.toCharArray();
        TrieNode[] current = this.root;
        for (int i = 0; i < chars.length; i++) {
            int index = chars[i] - 'a';
            if (Objects.isNull(current[index])) {
                current[index] = new TrieNode();
            }
            if (i == chars.length - 1) {
                current[index].isEnd = true;
            }
            current = current[index].alphabet;
        }
    }

    /**
     * Returns if the word is in the trie.
     */
    public boolean search(String word) {
        char[] chars = word.toCharArray();
        TrieNode[] current = this.root;
        for (int i = 0; i < chars.length; i++) {
            int index = chars[i] - 'a';
            if (Objects.isNull(current[index])) {
                return false;
            }
            if (i == chars.length - 1) {
                return current[index].isEnd;
            }
            current = current[index].alphabet;
        }
        return false;
    }

    /**
     * Returns if there is any word in the trie that starts with the given prefix.
     */
    public boolean startsWith(String prefix) {
        char[] chars = prefix.toCharArray();
        TrieNode[] current = this.root;
        for (int i = 0; i < chars.length; i++) {
            int index = chars[i] - 'a';
            if (Objects.isNull(current[index])) {
                return false;
            }
            current = current[index].alphabet;
        }
        return true;
    }
}

private void test() {
    Trie trie = new Trie();
    trie.insert("apple");
    System.out.println(trie.search("apple"));
    System.out.println(!trie.search("app"));
    System.out.println(trie.startsWith("app"));
    trie.insert("app");
    System.out.println(trie.search("app"));
}