/**
 * 字典树（英文字典树）
 * @author zzr
 * @create 2023-11-09-12:04
 */
public class Trie {

    /**
     * 结点类
     */
    static class Node{
        private Node[] children;//孩子指针
        private boolean isEnd;//是否为一个字符串结束字符

        public Node() {
            children=new Node[26];//26个英文字母指针
        }
    }

    private Node root;//根结点

    public Trie() {
        root=new Node();
    }

    /**
     * 插入
     * @param word 待添加字符串
     */
    public void insert(String word) {
        Node curr=root;//用于搜素
        for (int i = 0; i < word.length(); i++) {
            int index=word.charAt(i)-'a';//对应字符指针索引
            if (curr.children[index]==null){//字符不存在，直接添加
                curr.children[index]=new Node();
            }
            //存在，更新当前指针，处理下一字符
            curr=curr.children[index];
        }
        //处理完所有字符，标记当前结点为结束字符
        curr.isEnd=true;
    }

    /**
     * 查找字符串
     * @param word
     * @return
     */
    public boolean search(String word) {
        Node curr=root;
        for (int i = 0; i < word.length(); i++) {
            int index=word.charAt(i)-'a';//对应字符指针索引
            if (curr.children[index]==null){
                return false;
            }
            curr=curr.children[index];
        }
        return curr.isEnd;//需搜索到结束结点才是一个字符串
    }

    /**
     * 查找前缀
     * @param prefix
     * @return
     */
    public boolean startsWith(String prefix) {
        Node curr=root;
        for (int i = 0; i < prefix.length(); i++) {
            int index=prefix.charAt(i)-'a';//对应字符指针索引
            if (curr.children[index]==null){
                return false;
            }
            curr=curr.children[index];
        }
        return true;
    }

}