LeetCode：208. Implement Trie (实现Trie树)

悠悠 2022-10-16 07:12 170阅读 0赞

> **文章最前**： 我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如果您对 Python、Java、AI、算法有兴趣，可以关注我的动态，一起学习，共同进步。

**相关文章：**

1.  **[LeetCode：55. Jump Game（跳远比赛）][LeetCode_55. Jump Game]**
2.  **[Leetcode：300. Longest Increasing Subsequence（最大增长序列）][Leetcode_300. Longest Increasing Subsequence]**
3.  **[LeetCode：560. Subarray Sum Equals K（找出数组中连续子串和等于k）][LeetCode_560. Subarray Sum Equals K_k]**

--------------------

**文章目录:**

题目描述：

java实现方式：

Python实现方式：

源码地址：

--------------------

### 题目描述： ###

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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/implement-trie-prefix-tree  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

--------------------

### java实现方式： ###

/**
     * 定义Node节点
     *
     * @author: zhangyu
     * @date: 2021/5/27
     */
    class Node {
    
        /**
         * 是否为单词的标志位
         */
        public boolean isWord;
        /**
         * 存储单词穿的map
         */
        public TreeMap<Character, Node> next;
    
        /**
         * 构造node节点的构造方法
         *
         * @param isWord 是否是word标志位
         */
        public Node(boolean isWord) {
            this.isWord = isWord;
            next = new TreeMap<>();
        }
    
        /**
         * 构造node节点的方法
         */
        public Node() {
            this(false);
        }
    }
    
    
    public class Trie {
        /**
         * 构造root节点
         */
        private Node root;
    
        /**
         * 构造trie树方法
         */
        public Trie() {
            root = new Node();
        }
    
        /**
         * 向Trie中添加单词
         * 时间复杂度：O(m), m为要查询字符串的长度
         * 空间复杂度：O(m), 最坏情况下没有公共节点，需要添加 m 个节点
         *
         * @param word 插入单词
         */
        public void insert(String word) {
            Node cur = root;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                if (cur.next.get(c) == null) {
                    cur.next.put(c, new Node());
                }
                cur = cur.next.get(c);
            }
            cur.isWord = true;
        }
    
        /**
         * 判断单词是否在 Trie 中
         * 时间复杂度：O(m), m为要查询字符串的长度
         * 空间复杂度：O(1)
         *
         * @param word 查找单词
         * @return 布尔值
         */
        public boolean search(String word) {
            Node cur = root;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                if (cur.next.get(c) == null) {
                    return false;
                }
                cur = cur.next.get(c);
            }
            return cur.isWord;
        }
    
        /**
         * 查询是否在Trie中有单词以prefix为前缀
         * 时间复杂度：O(m), m为要查询字符串的长度
         * 空间复杂度：O(1)
         *
         * @param prefix 前缀字符串
         * @return 布尔值
         */
        public boolean startsWith(String prefix) {
            Node cur = root;
            for (int i = 0; i < prefix.length(); i++) {
                char c = prefix.charAt(i);
                if (cur.next.get(c) == null) {
                    return false;
                }
                cur = cur.next.get(c);
            }
            return true;
        }
    }

时间复杂度：O(m) , 字符串的长度

空间复杂度：O(n)

--------------------

### Python实现方式： ###

class Node:
    
        def __init__(self):
            '''
                构造Node节点
            Args:
                is_word: 判断是否是单词
            '''
            self.is_word = False
            self.children = dict()
    
    
    class Trie:
        root = Node()
    
        def __int__(self):
            root = Node()
    
        def insert(self, word: str) -> None:
            '''
                将单词插入到Trie树中
            Args:
                word: 单词
            Returns:
                None
            '''
            cur = self.root
            for i in range(len(word)):
                c = word[i]
                if c not in cur.children:
                    cur.children[c] = Node()
                cur = cur.children[c]
            cur.is_word = True
    
        def search(self, word) -> bool:
            '''
                查找单词
            Args:
                word: 单词
            Returns:
                布尔值
            '''
            cur = self.root
            for i in range(len(word)):
                c = word[i]
                if c not in cur.children:
                    return False
                cur = cur.children[c]
            return cur.is_word
    
        def starts_with(self, prefix: str) -> bool:
            '''
                字符串开始位置
            Args:
                prefix:前缀
            Returns:
                布尔值
            '''
            cur = self.root
            for i in range(len(prefix)):
                c = prefix[i]
                if c not in cur.children:
                    return False
                cur = cur.children[c]
            return True

时间复杂度：O(m)  ,字符串的长度

空间复杂度：O(n)

--------------------

### 源码地址： ###

[https://github.com/zhangyu345293721/leetcode][https_github.com_zhangyu345293721_leetcode]

[github]: https://github.com/zhangyu345293721
[LeetCode_55. Jump Game]: https://blog.csdn.net/zy345293721/article/details/84991870
[Leetcode_300. Longest Increasing Subsequence]: https://blog.csdn.net/zy345293721/article/details/84984249
[LeetCode_560. Subarray Sum Equals K_k]: https://blog.csdn.net/zy345293721/article/details/84952201
[https_github.com_zhangyu345293721_leetcode]: https://github.com/zhangyu345293721/leetcode