class Trie {
    /**
* 經(jīng)過該節(jié)點(diǎn)的字符串的下層節(jié)點(diǎn)
*/
    Map<Character, Trie> next;
    /**
* 該節(jié)點(diǎn)是否是一個(gè)字符串的結(jié)束
*/
    boolean isEnd;

    public Trie() {
        this.next = new HashMap<>();
        this.isEnd = false;
    }

}

public void insert(String word) {
    //初始默認(rèn)為根節(jié)點(diǎn)，根節(jié)點(diǎn)不包含任何字符
    Trie cur = this;
    //遍歷該字符串的字符數(shù)組
    for (char c : word.toCharArray()) {
        //如果該節(jié)點(diǎn)的下層不包含此字符，那么加入一個(gè)新節(jié)點(diǎn)進(jìn)去
        if (!cur.next.containsKey(c)) {
            cur.next.put(c, new Trie());
        }
        //查找下一層節(jié)點(diǎn)
        cur = cur.next.get(c);
    }
    //遍歷字符串完畢，最后的節(jié)點(diǎn)isEnd置為true，表示一個(gè)字符串的結(jié)束
    cur.isEnd = true;
}

/**
 * 查找字符串
 */
public boolean search(String word) {
    Trie end = searchPrefix(word);
    return end != null && end.isEnd;
}

/**
 * 匹配前綴
 */
public boolean startsWith(String prefix) {
    return searchPrefix(prefix) != null;
}

private Trie searchPrefix(String prefix) {
    //初始默認(rèn)為根節(jié)點(diǎn)，根節(jié)點(diǎn)不包含任何字符
    Trie cur = this;
    //遍歷該字符串的字符數(shù)組
    for (char c : prefix.toCharArray()) {
        //如果該節(jié)點(diǎn)的下層不包含此字符，那么直接返回null
        if (!cur.next.containsKey(c)) {
            return null;
        }
        //查找下一層節(jié)點(diǎn)
        cur = cur.next.get(c);
    }
    return cur;
}

class Trie {
    /**
     * 經(jīng)過該節(jié)點(diǎn)的字符串的下層節(jié)點(diǎn)
     */
    Map<Character, Trie> next;
    /**
     * 該節(jié)點(diǎn)是否是一個(gè)字符串的結(jié)束
     */
    boolean isEnd;

    public Trie() {
        this.next = new HashMap<>();
        this.isEnd = false;
    }

    public void insert(String word) {
        //初始默認(rèn)為根節(jié)點(diǎn)，根節(jié)點(diǎn)不包含任何字符
        Trie cur = this;
        //遍歷該字符串的字符數(shù)組
        for (char c : word.toCharArray()) {
            //如果該節(jié)點(diǎn)的下層不包含此字符，那么加入一個(gè)新節(jié)點(diǎn)進(jìn)去
            if (!cur.next.containsKey(c)) {
                cur.next.put(c, new Trie());
            }
            //查找下一層節(jié)點(diǎn)
            cur = cur.next.get(c);
        }
        //遍歷字符串完畢，最后的節(jié)點(diǎn)isEnd置為true，表示一個(gè)字符串的結(jié)束
        cur.isEnd = true;
    }

    /**
     * 查找字符串
     */
    public boolean search(String word) {
        Trie end = searchPrefix(word);
        return end != null && end.isEnd;
    }

    /**
     * 匹配前綴
     */
    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }

    private Trie searchPrefix(String prefix) {
        //初始默認(rèn)為根節(jié)點(diǎn)，根節(jié)點(diǎn)不包含任何字符
        Trie cur = this;
        //遍歷該字符串的字符數(shù)組
        for (char c : prefix.toCharArray()) {
            //如果該節(jié)點(diǎn)的下層不包含此字符，那么直接返回null
            if (!cur.next.containsKey(c)) {
                return null;
            }
            //查找下一層節(jié)點(diǎn)
            cur = cur.next.get(c);
        }
        return cur;
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("你是xxl嗎？");
    }
}