1. 题目

实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。 示例: 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 说明:

你可以假设所有的输入都是由小写字母 a-z 构成的。 保证所有输入均为非空字符串。

Related Topics 设计 字典树 👍 496 👎 0

1.1 先理解前缀树

假设刚开始我们，有一个空节点，现在我们有一个操作，往这个空的节点上insert字符串“abc”, 那么我们按照下面的步骤insert：

process: 1、首先看当前节点有没有指向字符’a’的路径，没有的话就创建指向’a’的路径，否则滑过到下一个字符，同样是看看有没有到该字符的路径。一直遍历完字符，并且都创建好了路径。如下图所示：

以上参考:

前缀树中存储的键值, 相当于被存储到了下一个指针中, 而没有存在结点中

Trie 前缀树是一个有根的树，其结点具有以下字段：

最多 RR 个指向子结点的链接，其中每个链接对应字母表数据集中的一个字母。本文中假定 RR 为 26，小写拉丁字母的数量。 布尔字段，以指定节点是对应键的结尾还是只是键前缀。

2. 题解

class Trie {
          
   
        private boolean isEnd = false;
        private Trie[] next = new Trie[26];

        /**
         * Initialize your data structure here.
         */
        public Trie() {
          
   

        }

        /**
         * Inserts a word into the trie.
         */

        public void insert(String word) {
          
   
            Trie root = this;
            char[] charArray = word.toCharArray();
            for (int i = 0; i < charArray.length; i++) {
          
   
                if (root.next[charArray[i] - a] == null) {
          
   
                    root.next[charArray[i] - a] = new Trie();
                }
                // 若已经存在该字母, 则插入下一个字母
                root = root.next[charArray[i] - a];
            }
            // 最后记得要将最后一个字母标志结束
            root.isEnd = true;
        }

        /**
         * Returns if the word is in the trie.
         */
        public boolean search(String word) {
          
   
            Trie root = this;
            char[] charArray = word.toCharArray();
            for (int i = 0; i < charArray.length; i++) {
          
   
                if (root.next[charArray[i] - a] == null) {
          
   
                    return false;
                }
                // 向下推进
                root = root.next[charArray[i] - a];
            }
            return root.isEnd;
        }

        /**
         * Returns if there is any word in the trie that starts with the given prefix.
         */
        public boolean startsWith(String prefix) {
          
   
            Trie root = this;
            char[] charArray = prefix.toCharArray();
            for (int i = 0; i < charArray.length; i++) {
          
   
                if (root.next[charArray[i] - a] == null) {
          
   
                    return false;
                }
                // 向下推进
                root = root.next[charArray[i] - a];
            }
            return true;
        }
    }