字典树

字典树（Trie）用于判断字符串是否存在或者是否具有某种字符串前缀。

字典树

为什么需要用字典树解决这类问题呢？假如我们有一个储存了近万个单词的字典，即使我们使用哈希，在其中搜索一个单词的实际开销也是非常大的，且无法轻易支持搜索单词前缀。然而 由于一个英文单词的长度 n 通常在 10 以内，如果我们使用字典树，则可以在 O(n)——近似 O(1) 的时间内完成搜索，且额外开销非常小。

构建字典树

尝试建立一个字典树，支持快速插入单词、查找单词、查找单词前缀的功能。

public class Trie {
    TrieNode root;
    public Trie(){
        root=new TrieNode();
    }
    //向字典树中插入一个词
    public void insert(String word){
        TrieNode tmp=root;
        for(int i=0;i<word.length();i++){
            if(null == tmp.childNode[word.charAt(i) - 'a']){
                tmp.childNode[word.charAt(i)-'a']=new TrieNode();
            }
            tmp=tmp.childNode[word.charAt(i)-'a'];
        }
        tmp.isVal=true;
    }
    //判断字典树里是否有一个词
    boolean search(String word){
        TrieNode tmp=root;
        for(int i=0;i<word.length();++i){
            if(tmp==null){
                break;
            }
            tmp=tmp.childNode[word.charAt(i)-'a'];
        }
        return tmp!=null?tmp.isVal:false;
    }
    
    //判断字典树是否有一个以词开始的前缀
    boolean startsWith(String prefix){
        TrieNode tmp=root;
        for(int i=0;i<prefix.length();i++){
            if(tmp==null){
                break;
            }
            tmp=tmp.childNode[prefix.charAt(i)-'a'];
        }
        return tmp!=null;
    }


    public static void main(String[] args) {
        Trie trie=new Trie();
        System.out.println(trie.search("apple"));//false
        trie.insert("apple");
        System.out.println(trie.search("apple"));//true
        System.out.println(trie.search("app"));//false
        System.out.println(trie.startsWith("app"));//true;
        trie.insert("app");
        System.out.println(trie.search("app"));//true

    }
}

class TrieNode{
    TrieNode[] childNode =new TrieNode[26];
    boolean isVal;
    TrieNode(){
        isVal=false;
        for(int i=0;i<26;i++){
            childNode[i]=null;
        }
    }
}