[LintCode/LeetCode] Implement Trie

付永剛發(fā)布于2019-08-14 15:23 / 3611人閱讀

摘要：首先，我們應(yīng)該了解字典樹的性質(zhì)和結(jié)構(gòu)，就會(huì)很容易實(shí)現(xiàn)要求的三個(gè)相似的功能插入，查找，前綴查找。既然叫做字典樹，它一定具有順序存放個(gè)字母的性質(zhì)。所以，在字典樹的里面，添加，和三個(gè)參數(shù)。

Problem

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

Notice

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

Example

insert("lintcode")
search("code") // return false
startsWith("lint") // return true
startsWith("linterror") // return false
insert("linterror")
search("lintcode) // return true
startsWith("linterror") // return true

Note

首先，我們應(yīng)該了解字典樹的性質(zhì)和結(jié)構(gòu)，就會(huì)很容易實(shí)現(xiàn)要求的三個(gè)相似的功能：插入，查找，前綴查找。
既然叫做字典樹，它一定具有順序存放26個(gè)字母的性質(zhì)。另外，為了實(shí)現(xiàn)和區(qū)別全詞查找和前綴查找，應(yīng)該有一個(gè)標(biāo)記。所以，在字典樹的class里面，添加ch，exist和children三個(gè)參數(shù)。

插入操作：建立結(jié)點(diǎn)pre，復(fù)制root。在pre的children[index]存放插入詞匯word的第i個(gè)字符（用數(shù)字0到25表示a~z的26個(gè)字母，記作index），依次類推。若當(dāng)前的children不存在，則建立大小為26的children結(jié)點(diǎn)數(shù)組。若children結(jié)點(diǎn)數(shù)組里的第index個(gè)TrieNode為空，則放入新的值為word.charAt(i)的TrieNode。然后pre前進(jìn)到當(dāng)前結(jié)點(diǎn)的children，pre.children[index]，繼續(xù)循環(huán)操作word的下一個(gè)字符。直到放入word的最后一個(gè)字符以后，修改pre.exist值為true，說明pre之前的分支完整放入了word。

查找操作：同插入一樣，復(fù)制root到結(jié)點(diǎn)pre，然后遍歷查找word的每一個(gè)字符word.charAt(i)，若循環(huán)里某個(gè)pre.children[index]不存在，或者word的最后一個(gè)字符的exist標(biāo)記為false，則返回false。否則，循環(huán)結(jié)束，返回true。

前綴查找操作：唯一和查找操作不同的地方，是不要求word的最后一個(gè)字符的exist標(biāo)記為true。只要遍歷完String prefix，就返回true。

Solution

class TrieNode {
    // Initialize your data structure here.
    boolean exist;
    char ch;
    TrieNode[] children;
    public TrieNode() {
        
    }
    public TrieNode(char ch) {
        this.ch = ch;
    }
}

public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // Inserts a word into the trie.
    public void insert(String word) {
        if (word == null || word.length() == 0) return;
        TrieNode pre = root;
        for (int i = 0; i < word.length(); i++) {
            if (pre.children == null) pre.children = new TrieNode[26];
            int index = word.charAt(i) - "a";
            if (pre.children[index] == null) {
                pre.children[index] = new TrieNode(word.charAt(i));
            }
            pre = pre.children[index];
            if (i == word.length()-1) pre.exist = true;
        }
    }

    // Returns if the word is in the trie.
    public boolean search(String word) {
        if (word == null || word.length() == 0) return false;
        TrieNode pre = root;
        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i) - "a";
            if (pre.children == null || pre.children[index] == null) return false;
            if (i == word.length()-1 && pre.children[index].exist == false) return false;
            pre = pre.children[index];
        }
        return true;
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    public boolean startsWith(String prefix) {
        if (prefix == null || prefix.length() == 0) return false;
        TrieNode pre = root;
        for (int i = 0; i < prefix.length(); i++) {
            int index = prefix.charAt(i) - "a";
            if (pre.children == null || pre.children[index] == null) return false;
            pre = pre.children[index];
        }
        return true;
    }
}