實現一個 Trie (前綴樹)，包含?insert,?search, 和?startsWith?這三個操作。

示例:

Trie trie = new Trie();

trie.insert("apple");
trie.search("apple"); ? // 返回 true
trie.search("app"); ? ? // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app"); ??
trie.search("app"); ? ? // 返回 true
說明:

你可以假設所有的輸入都是由小寫字母?a-z?構成的。
保證所有輸入均為非空字符串。

前綴樹介紹

public class Trie {private boolean is_string=false;private Trie next[]=new Trie[26];public Trie(){}public void insert(String word){//插入單詞Trie root=this;char w[]=word.toCharArray();for(int i=0;i<w.length;++i){if(root.next[w[i]-'a']==null)root.next[w[i]-'a']=new Trie();root=root.next[w[i]-'a'];}root.is_string=true;}public boolean search(String word){//查找單詞Trie root=this;char w[]=word.toCharArray();for(int i=0;i<w.length;++i){if(root.next[w[i]-'a']==null)return false;root=root.next[w[i]-'a'];}return root.is_string;}public boolean startsWith(String prefix){//查找前綴Trie root=this;char p[]=prefix.toCharArray();for(int i=0;i<p.length;++i){if(root.next[p[i]-'a']==null)return false;root=root.next[p[i]-'a'];}return true;}
}

?