逐步決議力扣208. 實作 Trie (前綴樹/字典樹)-有解無憂

https://leetcode-cn.com/problems/implement-trie-prefix-tree/

沒看答案前隨便寫了下發現能過，但這完全是直接調輪子亂寫

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;
        }
    }