逐步解析力扣208. 实现 Trie (前缀树/字典树)

admin • 2022-01-05 08:03 • 程序人生

没看答案前随便写了下发现能过，但这完全是直接调轮子乱写

class Trie {
        Set<String> a = new HashSet<>();

        public Trie() {

        }

        public void insert(String word) {
            a.add(word);
        }

        public boolean search(String word) {
            return a.contains(word);
        }

        public boolean startsWith(String prefix) {
            for (String s:a) {
                if (s.startsWith(prefix)) return true;
            }
            return false;
        }
}

主要目的是要学习前缀树（字典树）

前缀树是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

时间复杂度：初始化为 O(1)，其余操作为 O(∣S∣)，其中 |S| 是每次插入或查询的字符串的长度

比用哈希表快了不少

其实看了代码之后就很好理解

class Trie {
        private Trie[] children;
        private boolean isEnd;

        public Trie() {
            children = new Trie[26];
            isEnd = false;
        }

        public void insert(String word) {
            Trie node = this;
            for (int i = 0; i < word.length(); i++) {
                char ch = word.charAt(i);
                int index = ch - 'a';
                if (node.children[index]==null) node.children[index] = new Trie();
                node = node.children[index];
            }
            node.isEnd = true;
        }

        public boolean search(String word) {
            Trie node = searchPrefix(word);
            return node !=null && node.isEnd;
        }
        private Trie searchPrefix(String prefix){
            Trie node = this;
            for (int i = 0; i < prefix.length(); i++) {
                char ch = prefix.charAt(i);
                int index = ch - 'a';
                if (node.children[index]==null) return null;
                node = node.children[index];
            }
            return node;
        }

        public boolean startsWith(String prefix) {
           return searchPrefix(prefix) !=null;
        }
    }