算法：day1

前缀树：

class Trie {
    private Trie[] childrenIndex;// 该节点下一个可能出现的所有字符的链接
    private boolean isEnd;// 该节点是否是最后一个字符
    // 初始化根节点
    public Trie() {
        childrenIndex = new Trie[26];
        isEnd = false;
    }
    
    public void insert(String word) {
        // 获得当前节点指针
        Trie curr = this;
        // 遍历字符
        for (char c : word.toCharArray()){
            // 得到该字符的数组中坐标
            int index = c - 'a';
            // 判断当前节点的下一个节点是否有该字符,如果没有则新建一个节点
            if (curr.childrenIndex[index]==null){
                curr.childrenIndex[index] = new Trie();
            }
            // 移动当前节点指针
            curr = curr.childrenIndex[index];
        }
        curr.isEnd = true;
    }
    
    public boolean search(String word) {
        // 当前指针指向根节点
        Trie curr = this;
        for (char c : word.toCharArray()){
            // 得到当前字符的坐标
            int index = c - 'a';
            // 该字符不在当前指针的下一个节点里
            if (curr.childrenIndex[index]==null){
                return false;
            }else {
                // 在下一个节点里，则移动指针
                curr = curr.childrenIndex[index];
            }
        }
        // 指针移动的时候，指向的节点可能是最后一个，也可能不是
        // 所有应该判断是否是最后一个，同时最后一个节点也不会为null
        if (curr!=null && curr.isEnd){
            return true;
        }
        return false;

    }
    
    public boolean startsWith(String prefix) {
        // 当前指针指向根节点
        Trie curr = this;
        for (char c : prefix.toCharArray()){
            // 得到当前字符的坐标
            int index = c - 'a';
            // 该字符不在当前指针的下一个节点里
            if (curr.childrenIndex[index]==null){
                return false;
            }else {
                // 在下一个节点里，则移动指针
                curr = curr.childrenIndex[index];
            }
        }
        // 指针移动的时候，指向的节点不可能为null
        return curr!=null;
    }
}