/**
     * Trie樹節(jié)點(diǎn)
     * 假設(shè)我們只做26個(gè)小寫字母下的匹配
     */
    public static class Node{
        //當(dāng)前節(jié)點(diǎn)值
        private char value;
        //當(dāng)前節(jié)點(diǎn)的孩子節(jié)點(diǎn)
        private Node[] childNode;
        //標(biāo)志當(dāng)前節(jié)點(diǎn)是否是某單詞結(jié)尾
        private boolean isTail;
        public Node(char value) {
            this.value = value;
        }
    }

Node root;
public void init() {
        root = new Node('\0');
        root.childNode = new Node[26];
}

/**
     * 將當(dāng)前串插入字典樹
     * @param chars
     */
    public void insertStr(char[] chars) {
        //首先判斷首字符是否已經(jīng)在字典樹中，然后判斷第二字符，依次往下進(jìn)行判斷，找到第一個(gè)不存在的字符進(jìn)行插入孩節(jié)點(diǎn)
        Node p = root;
        //表明當(dāng)前處理到了第幾個(gè)字符
        int chIndex = 0;
        while (chIndex < chars.length) {
            while (chIndex < chars.length && null != p) {
                Node[] children = p.childNode;
                boolean find = false;
                for (Node child : children) {
                    if (null == child) {continue;}
                    if (child.value == chars[chIndex]) {
                        //當(dāng)前字符已經(jīng)存在，不需要再進(jìn)行存儲(chǔ)
                        //從當(dāng)前節(jié)點(diǎn)出發(fā)，存儲(chǔ)下一個(gè)字符
                        p = child;
                        ++ chIndex;
                        find = true;
                        break;
                    }
                }
                if (Boolean.TRUE.equals(find)) {
                    //在孩子中找到了 不用再次存儲(chǔ)
                    break;
                }
                //如果把孩子節(jié)點(diǎn)都找遍了，還沒有找到這個(gè)字符，直接將這個(gè)字符加入當(dāng)前節(jié)點(diǎn)的孩子節(jié)點(diǎn)
                Node node = new Node(chars[chIndex]);
                node.childNode = new Node[26];
                children[chars[chIndex] - 'a'] = node;
                p = node;
                ++ chIndex;
            }
        }
        //字符串中字符全部進(jìn)入tire樹中后，將最后一個(gè)字符所在節(jié)點(diǎn)標(biāo)志為結(jié)尾節(jié)點(diǎn)
        p.isTail = true;
    }

 /**
     * 查看當(dāng)前字符串是否可以在trie中找到
     * @param str 主串
     * @return true/false
     */
    public boolean isMatch(String str) {
        //從root開始進(jìn)行匹配，只要有一個(gè)找不到即為匹配失敗
        char[] chars = str.toCharArray();
        int chIndex = 0;
        Node p = root;
        while (null != p) {
            Node[] children = p.childNode;
            boolean flag = false;
            for (Node child : children) {
                if (null == child) {continue;}
                if (child.value == chars[chIndex]) {
                    flag = true;
                    p = child;
                    ++ chIndex;
                    //當(dāng)比較最后一個(gè)字符的時(shí)候，這個(gè)字符需要是結(jié)尾字符才能完全匹配
                    if (chIndex == chars.length && p.isTail) {
                        return true;
                    }
                    break;
                }
            }
            if (Boolean.FALSE.equals(flag)) {
                return false;
            }
        }
        return false;
    }

public static void main(String[] args) {
        //he, him, lot, a
        //初始化Tire樹
        Trie trie = new Trie();
        trie.init();
        //構(gòu)建Tire樹，只有以下單詞才是有效單詞
        trie.insertStr("he".toCharArray());
        trie.insertStr("him".toCharArray());
        trie.insertStr("lot".toCharArray());
        trie.insertStr("a".toCharArray());
        //匹配字符串是否為有效單詞
        System.out.println(trie.isMatch("lot"));
        System.out.println(trie.isMatch("lit"));

    }

 /**
     * 找到所有以str為前綴的字符串
     * @param str 前綴串
     * @return 所有以str為前綴的單詞
     */
    public List<String> findStrPrefix(String str) {
        //根據(jù)str首先找到str最后一個(gè)字符，然后從這個(gè)字符出發(fā)，找到所有字符串
        List<String> result = new ArrayList<>();
        char[] chars = str.toCharArray();
        //分成兩步走
        //1。找到str最后一個(gè)自字符在字典樹中的node
        //2。從該node出發(fā)，找到所有的結(jié)尾node，即為以str為前綴的字符串
        int chIndex = 0;
        Node p = root;
        while (null != p && chIndex < chars.length) {
            Node[] children = p.childNode;
            boolean flag = false;
            for (Node child : children) {
                if (null == child) {continue;}
                if (child.value == chars[chIndex]) {
                    //已經(jīng)找到
                    p = child;
                    flag = true;
                    ++ chIndex;
                    break;
                }
            }
            //如果沒有找到，直接返回空
            if (Boolean.FALSE.equals(flag)) {
                return null;
            }
        }
        //找到了最后一個(gè)節(jié)點(diǎn)
        //深度優(yōu)先遍歷，查找所有尾節(jié)點(diǎn)
        this.dfs(p, new StringBuilder(str), result);
        return result;
    }

    public void dfs(Node p, StringBuilder str, List<String> result) {
        Node[] children = p.childNode;
        for (Node child : children) {
            if (null == child) {
                continue;
            }
            str.append(child.value);
            if (child.isTail) {
                result.add(str.toString());
            }
            //再遞歸查當(dāng)前節(jié)點(diǎn)的孩子節(jié)點(diǎn)
            dfs(child, str, result);
            //需要將剛剛set進(jìn)去的節(jié)點(diǎn)刪除，否則影響當(dāng)前節(jié)點(diǎn)的下一個(gè)孩子節(jié)點(diǎn)
            //舉個(gè)例子，h的孩子節(jié)點(diǎn)有e，i，當(dāng)e放進(jìn)去之后不拿出來，在遍歷到i的時(shí)候，就會(huì)形成hei
            str.setLength(str.length() - 1);
        }
    }

public static void main(String[] args) {
        //he, him, lot, a
        //初始化Tire樹
        Trie trie = new Trie();
        trie.init();
        //構(gòu)建Tire樹，只有以下單詞才是有效單詞
        trie.insertStr("he".toCharArray());
        trie.insertStr("him".toCharArray());
        trie.insertStr("lot".toCharArray());
        trie.insertStr("a".toCharArray());
        //匹配字符串是否為有效單詞
        List<String> strings = trie.findStrPrefix("h");
    }