唯客微博客

专注于计算机，嵌入式领域的技术

0%

208. 实现 Trie (前缀树)

发表于 更新于 分类于

题目

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

请你实现 Trie 类：

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

示例：

输入 ["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]] 输出 [null, null, true, false, true, null, true]

解释 Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); // 返回 True trie.search("app"); // 返回 False trie.startsWith("app"); // 返回 True trie.insert("app"); trie.search("app"); // 返回 True

提示：

  • 1 <= word.length, prefix.length <= 2000
  • word 和 prefix 仅由小写英文字母组成
  • insert、search 和startsWith 调用次数 总计 不超过 3 * 104 次

思路

  • 题目要求实现一个Trie，包含插入、查找和查找前缀三个方法。
  • Trie树也称字典树，因为其效率很高，所以在在字符串查找、前缀匹配等中应用很广泛，其高效率是以空间为代价的。
  • 原理：利用串构建一个字典树，这个字典树保存了串的公共前缀信息，因此可以降低查询操作的复杂度。
  • 定义结点Node里包含一个ch(存储字符)、isEnd(表示这个结点是否是一个词的结尾)和一个next(存储下一个字符结点)。

  1. 定义一个根结点root作为整棵树的查找起点。

  2. 比如插入一个词"中国制造"：

    我们从root开始，依次往下查找'中','国','制','造'：如果在结点n的下一个字符列表里没有找到我们想要的字符ch，我们就增加新结点到结点n的next。

  3. 查找一个词"中国制造"：

    我们从root开始，依次往下查找'中','国','制','造'：如果在结点n的下一个字符列表里没有找到我们想要的字母ch，那么说明不存在，返回false;如果有，那么继续往下找，直到查找的词"中国制造"找到最后一位，这时候我们判断一下这个位置的isWord是否为true，如果为true说明这是一个完整单词，否则只是部分，返回False。

  4. 查找一个前缀

查找一个前缀和查找一个单词的区别就是，当我们想要查找的前缀找到最后一位，不需要判断是否是完整的单词，直接返回true即可。如果不能全部找到则返回False。

复杂度

  • 空间复杂度: 字典树每个节点都需要用一个列表存储下一个字符结点，所以空间复杂度较高。
  • 时间复杂度: 假设所有插入字符串长度之和为n，构建字典树的时间复杂度为O(n)；假设要查找的所有字符串长度之和为k，查找的时间复杂度为O(k)。因此时间复杂度为O(n+k)

代码

下面代码列出了insert、search、startswith、delete四种操作，题目中只要求insert、search、startsWith。

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
import java.util.LinkedList;
import java.util.List;

public class Trie {
    static class Node {
        public char ch;
        public boolean isEnd;
        public List<Node> next;


        public Node(char ch) {
            this.ch = ch;
            this.isEnd = false;
            this.next = new LinkedList<>();
        }


        public Node findNode(char ch) {
            for (Node node : next) {
                if (node.ch == ch) {
                    return node;
                }
            }

            return null;
        }
    }

    private Node root;

    public Trie() {
        root = new Node('\0');
    }

    public void insert(String word) {
        Node current = root;
        int n = word.length();
        for (int i = 0; i < n; i++) {
            char ch = word.charAt(i);
            Node node = current.findNode(ch);
            if (node == null) {
                node = new Node(ch);
                current.next.add(node);
            }
            current = node;
        }

        current.isEnd = true;
    }

    public boolean search(String word) {
        Node current = root;
        int n = word.length();
        for (int i = 0; i < n; i++) {
            char ch = word.charAt(i);
            Node node = current.findNode(ch);
            if (node == null) {
                return false;
            }
            else {
                current = node;
            }
        }

        return current.isEnd;
    }

    public boolean startWith(String prefix) {
        Node current = root;
        int n = prefix.length();
        for (int i = 0; i < n; i++) {
            char ch = prefix.charAt(i);
            Node node = current.findNode(ch);
            if (node == null) {
                return false;
            }
            else {
                current = node;
            }
        }

        return true;
    }


    public boolean delete(String word) {
        Node current = root;
        int n = word.length();
        List<Node> path = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            char ch = word.charAt(i);
            Node node = current.findNode(ch);
            if (node == null) {
                return false;
            }
            else {
                path.add(node);
                current = node;
            }
        }

        boolean isDelete = false;
        Node child = null;
        for (int i = path.size() - 1; i >= 0; i--) {
            Node node = path.get(i);
            if (isDelete) {
                node.next.remove(child);
            }
            if (node.next.isEmpty() && node.isEnd) {
                isDelete = true;
                child = node;
            }
        }

        return true;
    }

}

Demo

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
public class TrieTreeDemo {

    public static void main(String[] args) {
        Trie tree = new Trie();
        tree.insert("北京");
        tree.insert("海淀区");
        tree.insert("中国");
        tree.insert("中国人民");
        tree.insert("中国制造");
        tree.insert("中关村");

        String word = "中国";
        //查找该词是否存在 Trid Tree 中
        boolean flag = tree.search(word);
        if (flag) {
            System.out.println("Trie Tree 中已经存在【" + word + "】");
        } else {
            System.out.println("Trie Tree 不包含【" + word + "】");
        }

        word = "中国人民";
        //查找该词是否存在 Trid Tree 中
        flag = tree.search(word);
        if (flag) {
            System.out.println("Trie Tree 中已经存在【" + word + "】");
        } else {
            System.out.println("Trie Tree 不包含【" + word + "】");
        }

        String prefix = "中关";
        flag = tree.startWith(prefix);
        if (flag) {
            System.out.println("Trie Tree 中已经存在【" + prefix + "】");
        } else {
            System.out.println("Trie Tree 不包含【" + prefix + "】");
        }

        word = "中国人民";
        //查找该词是否存在 Trid Tree 中
        flag = tree.delete(word);

        //查找该词是否存在 Trid Tree 中
        flag = tree.search(word);
        if (flag) {
            System.out.println("Trie Tree 中已经存在【" + word + "】");
        } else {
            System.out.println("Trie Tree 不包含【" + word + "】");
        }

        word = "中国";
        //查找该词是否存在 Trid Tree 中
        flag = tree.search(word);
        if (flag) {
            System.out.println("Trie Tree 中已经存在【" + word + "】");
        } else {
            System.out.println("Trie Tree 不包含【" + word + "】");
        }

        word = "中国制造";
        //查找该词是否存在 Trid Tree 中
        flag = tree.search(word);
        if (flag) {
            System.out.println("Trie Tree 中已经存在【" + word + "】");
        } else {
            System.out.println("Trie Tree 不包含【" + word + "】");
        }

    }
}
-------------本文结束感谢您的阅读-------------

本文标题:208. 实现 Trie (前缀树)

文章作者:Vinx

发布时间:2023年04月25日 - 09:21

最后更新:2023年09月19日 - 08:48

原始链接:https://blog.vinkvin.com/post/84/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。