实现Trie(前缀树)

发表于
本文字数： 3.8k 阅读时长 ≈ 3 分钟

LeetCode每日一题，208. 实现Trie(前缀树)

先看题目描述

c2dFde.png

算法和思路

有序集

这个是最开始想到的方法，使用有序集 words 存储字符串，words 中字符串是按字典序升序排列的，插入操作就直接将字符串加入 words 中即可，search 操作就判断 words 中是否包括目标字符串即可

startsWith 操作较为麻烦，方法是使用有序集的 subSet 函数，例如对字符串 “abc” 进行 startsWith 操作，字典序排在以 “abc” 为前缀的字符串之后的字符串为 “abd”，那么就调用 words.subSet(“abc”, “abd”)，判断得到的集合大小是否大于 0 即可；而对应 “zzz” 这种，由于找不到以它为前缀的字符串的一个上界，于是就调用 words.tailSet(“zzz”)

字典树

这个是看题解才知道的方法，意识到这个才应该是正统的解法

Trie，又称前缀树或字典树，是一棵有根树，其每个节点包含以下字段：

  • 指向子节点的指针数组 children，对于本题而言，数组长度为 26，children[0] 对应 a，…，children[25] 对应 z
  • 布尔字段 isEnd，表示该节点是否为字符串的结尾

插入字符串：

我们从字典树的根开始，插入字符串。对于当前字符对应的子节点，有两种情况：

  • 子节点存在。沿着指针移动到子节点，继续处理下一个字符
  • 子节点不存在。创建一个新的子节点，记录在 children 数组的对应位置上，然后沿着指针移动节点，继续搜索下一个字符

重复上述步骤，直到处理字符串的最后一个字符，然后将当前节点标记为字符串的结尾

查找前缀：

我们从字典树的根开始，查找前缀。对于当前字符对应的子节点，有两种情况：

  • 子节点存在。沿着指针移动到子节点，继续搜索下一个字符
  • 子节点不存在，说明字典树中不包含该前缀，返回 false

重复上述步骤，直到返回 false 或搜索完前缀的最后一个字符

若搜索到了前缀的末尾，则说明字典树中存在该前缀。此外，若前缀末尾对应节点的 isEnd 为 true，则说明字典树中存在该字符串

算法源码

有序集

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
class Trie {

    private TreeSet<String> words = new TreeSet<>();

    /** Initialize your data structure here. */
    public Trie() {
        
    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
        words.add(word);
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        return words.contains(word);
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        int index = prefix.length() - 1;
        StringBuilder end = new StringBuilder(prefix);
        while (index >= 0 && end.charAt(index) == 'z') {
            end.deleteCharAt(end.length() - 1);
            index--;
        }
        if (index < 0) {
            return words.tailSet(prefix).size() > 0;
        } else {
            end.setCharAt(index, (char)(end.charAt(index) + 1));
            return words.subSet(prefix, end.toString()).size() > 0;
        }
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

字典树

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
class Trie {
    private boolean isEnd;
    private Trie[] children;

    /** Initialize your data structure here. */
    public Trie() {
        isEnd = false;
        children = new Trie[26];
    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
        Trie node = this;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                node.children[index] = new Trie();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        Trie node = this;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                return false;
            }
            node = node.children[index];
        }
        return node.isEnd;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        Trie node = this;
        for (char c : prefix.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                return false;
            }
            node = node.children[index];
        }
        return true;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */