package code;



/**

 * 前缀树(单词查找树)

 * 是一种树形结构; 用于保存大量的字符串。

 * 优点：利用字符串的公共前缀来节约存储空间。

 * 字母放在路径上，节点上存储到该节点的字符数pass以及以该节点为终点的字符数end

 *

 * @Author jiucaiyuan  2022/4/15 23:30

 * @mail services@jiucaiyuan.net

 */



public class TrieTree {



    public static class TrieNode {

        /**

         * 到该路径的次数

         */

        public int pass;

        /**

         * 以该路径为结尾的次数

         */

        public int end;

        /**

         * 当前节点到字符x的路径是否有

         * 如果有，则路径是nexts['x'-'a'] != null，具体次数是nexts['x'-'a'].pass，作为结果的次数为nexts['x'-'a'].end

         * 如果没有，则路径是nexts['x'-'a'] == null

         * 【注意】

         * 1.如果字符不只是a~z，特别多，可以用 `HashMap<Char,Node> nexts` 类型来表示

         * 2.如果需要下游路是有序组织的，可以使用`TreeMap<Char,Node> nexts`有序表来表示

         */

        public TrieNode[] nexts;



        public TrieNode() {

            pass = 0;

            end = 0;

            //nexts[0] == null,表示没有走向`a`的路

            //nexts[0] != null,表示有走向`a`的路

            //...

            //nexts[25] != null,表示有走向`z`的路

            nexts = new TrieNode[26];

        }

    }



    public static class Trie {

        /**

         * root.pass 表示加入前缀树树中单词（字符串）个数

         * root.end 表示加入前缀树中空字符串的个数

         * node.pass 表示加入到前缀树中以root到当前字符的字符串为前缀的字符串个数

         * node.end 表示加入到前缀树中以root到当前字符的字符串的个数

         */

        private TrieNode root;



        public Trie() {

            root = new TrieNode();

        }



        /**

         * 向前缀树中加入单词 （实现只支持小写字母a~z组成的单词）

         *

         * @param word

         */

        public void insert(String word) {

            if (word == null) {

                return;

            }

            char[] chs = word.toCharArray();

            TrieNode node = root;

            node.pass++;

            int index = 0;

            //从左往右遍历字符

            for (int i = 0; i < chs.length; i++) {

                index = chs[i] - 'a';  //由字符，对应成走哪天路

                if (node.nexts[index] == null) {

                    node.nexts[index] = new TrieNode();

                }

                //经过某条路时，边的to节点node记录经过信息

                node = node.nexts[index];

                node.pass++;

            }

            //加完该字符串后，结尾数累加1

            node.end++;

        }



        /**

         * 删除前缀树中某个字符串

         *

         * @param word

         */

        public void delete(String word) {

            if (search(word) == 0) {  //确定在树中，再进行删除操作

                return;

            }

            char[] chs = word.toCharArray();

            TrieNode node = root;

            node.pass--;

            int index = 0;

            for (int i = 0; i < chs.length; i++) {

                index = chs[i] - 'a';

                if (--node.nexts[index].pass == 0) {

                    node.nexts[index] = null;  //如果删除此字符串后，没有通过了，设置为null

                    return;

                }

                node = node.nexts[index];

            }

            node.end--;

        }



        /**

         * 搜索字符串，返回该字符串之前加入过几次

         *

         * @param word

         * @return

         */

        public int search(String word) {

            if (word == null) {

                return 0;

            }

            char[] chs = word.toCharArray();

            TrieNode node = root;

            int index = 0;

            //从左往右遍历字符

            for (int i = 0; i < chs.length; i++) {

                index = chs[i] - 'a';  //由字符，对应成走哪条路

                if (node.nexts[index] == null) {

                    return 0;

                }

                node = node.nexts[index];

            }

            //找到最后一个字符，返回该路径为结尾的次数

            return node.end;

        }



        /**

         * 加入的字符串当中，有几个是以prefix字符串为前缀的

         *

         * @param prefix

         * @return

         */

        public int prefixNumber(String prefix) {

            if (prefix == null) {

                return 0;

            }

            char[] chs = prefix.toCharArray();

            TrieNode node = root;

            int index = 0;

            for (int i = 0; i < chs.length; i++) {

                index = chs[i] - 'a';  //由字符，对应成走哪条路

                if (node.nexts[index] == null) {

                    return 0;

                }

                node = node.nexts[index];

            }

            //找到最后一个字符，返回该路径通过的次数

            return node.pass;

        }

    }

}