題目

Trie（發(fā)音類似 "try"）或者說 前綴樹 是一種樹形數(shù)據(jù)結(jié)構(gòu)濒生，用于高效地存儲(chǔ)和檢索字符串?dāng)?shù)據(jù)集中的鍵结耀。這一數(shù)據(jù)結(jié)構(gòu)有相當(dāng)多的應(yīng)用情景抑党，例如自動(dòng)補(bǔ)完和拼寫檢查润绎。

請(qǐng)你實(shí)現(xiàn) Trie 類：

Trie() 初始化前綴樹對(duì)象撬碟。
void insert(String word) 向前綴樹中插入字符串 word 。
boolean search(String word) 如果字符串 word 在前綴樹中莉撇，返回 true（即呢蛤，在檢索之前已經(jīng)插入）；否則棍郎，返回 false 其障。
boolean startsWith(String prefix) 如果之前已經(jīng)插入的字符串 word 的前綴之一為 prefix ，返回 true 坝撑；否則静秆，返回 false 。

示例：

輸入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
輸出
[null, null, true, false, true, null, true]

解釋
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

提示：

1 <= word.length, prefix.length <= 2000
word 和 prefix 僅由小寫英文字母組成
insert巡李、search 和 startsWith 調(diào)用次數(shù) 總計(jì) 不超過 3 * 104 次

思路：

定義一個(gè)新的內(nèi)部類Node抚笔，用isWord標(biāo)記該位置是否是一個(gè)單詞，用next指向下一個(gè)節(jié)點(diǎn)
insert侨拦、search和startWith操作的時(shí)間復(fù)雜度均是O(n)殊橙，其中n為待插入字符串或待查詢字符串或前綴的長度。

JAVA代碼：

class Trie {
    private class Node{
        private boolean isWord;
        private HashMap<Character, Node> next;
        public Node(boolean isWord) {
            this.isWord = isWord;
            this.next = new HashMap<>();
        }
        public Node() {
            this(false);
        }
    }
    private Node root;
    private int size;
    public Trie() {
        root = new Node();
        size = 0;
    }
    public void insert(String word) {
        Node cur = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if(cur.next.get(c) == null) {
                cur.next.put(c, new Node());
            }
            cur = cur.next.get(c);
        }
        if(!cur.isWord) {
            cur.isWord = true;
            size++;
        }
    }
    public boolean search(String word) {
        Node cur = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if(cur.next.get(c) == null) {
                return false;
            }
            cur = cur.next.get(c);
        }
        return cur.isWord;
    }
    public boolean startsWith(String prefix) {
        Node cur = root;
        for (int i = 0; i < prefix.length(); i++) {
            char c = prefix.charAt(i);
            if(cur.next.get(c) == null) {
                return false;
            }
            cur = cur.next.get(c);
        }
        return true;
    }
}