Description

Implement a trie with insert, search, and startsWith methods.

Note:
You may assume that all inputs are consist of lowercase letters a-z.

Solution

Array Trie, insert time O(len), search time O(len), startsWith time O(len)

Reference: 小白詳解 Trie 樹(shù)

很多文章里將這種實(shí)現(xiàn)稱為“標(biāo)準(zhǔn) Trie 樹(shù)”，但其實(shí)它只是 Trie 眾多實(shí)現(xiàn)中的一種而已，由于這種實(shí)現(xiàn)結(jié)構(gòu)簡(jiǎn)單，檢索效率很好，作為講解示例很不錯(cuò)，因此特地改稱其為“經(jīng)典 Trie 樹(shù)”，這里引用一下別人家的示例圖[2]：

abc、d、da、dda 四個(gè)字符串構(gòu)成的 Trie 樹(shù)，如果是字符串會(huì)在節(jié)點(diǎn)的尾部進(jìn)行標(biāo)記。沒(méi)有后續(xù)字符的 branch 分支指向NULL

Array Trie

如上圖，這種實(shí)現(xiàn)的特點(diǎn)是：每個(gè)節(jié)點(diǎn)都由指針數(shù)組存儲(chǔ)，每個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)都位于一個(gè)數(shù)組之中，每個(gè)數(shù)組都是完全一樣的。對(duì)于英文而言，每個(gè)數(shù)組有27個(gè)指針，其中一個(gè)作為詞的終結(jié)符，另外 26 個(gè)依次代表字母表中的一個(gè)字母，對(duì)應(yīng)指針指向下一個(gè)狀態(tài)，若沒(méi)有后續(xù)字符則指向NULL。由于數(shù)組取詞的復(fù)雜度為O(1)，因此這種實(shí)現(xiàn)的 Trie 樹(shù)效率非常的高，比如要在一個(gè)節(jié)點(diǎn)中寫入字符“c”,則直接在相應(yīng)數(shù)組的第三個(gè)位置標(biāo)入狀態(tài)即可，而要確定字母“b”是否在現(xiàn)有節(jié)點(diǎn)的子節(jié)點(diǎn)之中，檢查子節(jié)點(diǎn)所在數(shù)組第二個(gè)元素是否為空即可，這種實(shí)現(xiàn)巧妙的利用了等長(zhǎng)數(shù)組中元素位置和值的一一對(duì)應(yīng)關(guān)系，完美的實(shí)現(xiàn)了了尋址、存值、取值的統(tǒng)一。

但其缺點(diǎn)也很明顯，它強(qiáng)制要求鏈路每一層都要有一個(gè)數(shù)組，每個(gè)數(shù)組都必須等長(zhǎng)，這在實(shí)際應(yīng)用中會(huì)造成大多數(shù)的數(shù)組指針空置（從上圖就可以看出），事實(shí)上，對(duì)于真實(shí)的詞典而言，公共前綴相對(duì)于節(jié)點(diǎn)數(shù)量而言還是太少，這導(dǎo)致絕大多數(shù)節(jié)點(diǎn)下并沒(méi)有太多子節(jié)點(diǎn)。而對(duì)于中文這樣具有大量單字的語(yǔ)言，若采取這樣的實(shí)現(xiàn)，空置指針的數(shù)量簡(jiǎn)直不可想象。因此，經(jīng)典 Trie 樹(shù)是一種典型的以“空間換時(shí)間”的實(shí)現(xiàn)方式。一般只是拿來(lái)用于課程設(shè)計(jì)和新手練習(xí)，很少實(shí)際應(yīng)用。

class Trie {
    private Node root;
    /** Initialize your data structure here. */
    public Trie() {
        root = new Node();
    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
        Node pre = root;
        
        for (int i = 0; i < word.length(); ++i) {
            int index = word.charAt(i) - 'a';
            if (pre.next[index] == null) {
                pre.next[index] = new Node();
            }
            pre = pre.next[index];
        }
        
        pre.isWord = true;  // don't forget
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        Node node = find(word);
        return node != null && node.isWord;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        return find(prefix) != null;
    }
    
    private Node find(String word) {
        Node pre = root;
        for (int i = 0; i < word.length() && pre != null; ++i) {
            pre = pre.next[word.charAt(i) - 'a'];
        }
        return pre;
    }
    
    class Node {
        Node[] next;
        boolean isWord;
        
        public Node() {
            next = new Node[26];
            isWord = false;
        }
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

HashMap Trie

class Trie {
    private TrieNode root;
    /** Initialize your data structure here. */
    public Trie() {
        root = new TrieNode();
    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
        TrieNode pre = root;
        
        for (int i = 0; i < word.length(); ++i) {
            char c = word.charAt(i);
            if (!pre.childrenMap.containsKey(c)) {
                pre.childrenMap.put(c, new TrieNode(c));
            }
            pre = pre.childrenMap.get(c);
        }
        
        pre.isWord = true;
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TrieNode pre = root;
        
        for (int i = 0; i < word.length(); ++i) {
            char c = word.charAt(i);
            if (!pre.childrenMap.containsKey(c)) {
                return false;
            }
            pre = pre.childrenMap.get(c);
        }
        
        return pre.isWord;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        TrieNode pre = root;
        
        for (int i = 0; i < prefix.length(); ++i) {
            char c = prefix.charAt(i);
            if (!pre.childrenMap.containsKey(c)) {
                return false;
            }
            pre = pre.childrenMap.get(c);
        }
    
        return true;
    }
    
    class TrieNode {
        char val;
        Map<Character, TrieNode> childrenMap;
        boolean isWord;
        
        public TrieNode() {
            val = ' ';
            childrenMap = new HashMap<>();
        }
        
        public TrieNode(char val) {
            this.val = val;
            childrenMap = new HashMap<>();
        }
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */