字典树leetcode.745

 class TrieTree {
            //一棵前缀，一棵后缀
            private Node root1;//根节点，没有值
            private Node root2;
            //内部节点类
            private class Node{
                private Node childs[];//以下标为26个字母,存储下一个节点
                private  boolean isLeaf;//是否为叶子节点
                private List<Integer> idxs;//经过该节点的单词索引
                public Node(){
                    childs=new Node[26];
                    isLeaf=false;
                    idxs=new ArrayList<>();
                }
                public boolean contains(char key){
                    return childs[key-'a']!=null;
                }
                public Node get(char key){
                    return childs[key-'a']==null?null:childs[key-'a'];
                }
                public void put(char key,Node n){
                    childs[key-'a']=n;
                }
            }
            public TrieTree(){
                root1=new Node();
                root2=new Node();
            }
            //添加字符串
            public void put(String word,int idx){
                put(root1,root2,word,idx);
            }
            private void put(Node root1,Node root2,String word,int idx){
                char[] chs=word.toCharArray();
                int n=chs.length;
                Node cur2=root2;
                Node cur1=root1;
                for (int i = 0; i < n; i++) {
                    //如果不包含其中某个字符,创建新节点
                    if(!cur1.contains(chs[i])){
                        cur1.put(chs[i],new Node());
                    }
                    if(!cur2.contains(chs[n-1-i])){
                        cur2.put(chs[n-1-i],new Node());
                    }
                    cur1=cur1.get(chs[i]);//如果包含则继续寻找下一个字符
                    cur2=cur2.get(chs[n-1-i]);
                    //对于某个单词，如果其经过某个节点，则记录到该节点
                    //那么查找某个前缀时，最后一个节点记录了所有具有该前缀的单词索引
                    cur1.idxs.add(idx);
                    cur2.idxs.add(idx);
                }
                //到达单词结尾
                cur1.isLeaf=true;
                cur2.isLeaf=true;
            }

            List<Integer> search(Node root,String pre,int idx){
                //到达结尾
                if(idx==pre.length())
                    return root.idxs;
                char c=pre.charAt(idx);
                if(root.get(c)!=null)
                    return search(root.get(c),pre,idx+1);
                else return null;

            }
        }


        TrieTree t;
        public WordFilter(String[] words) {
            t=new TrieTree();
            for(int i=0;i<words.length;i++){
                t.put(words[i],i);
            }
        }
        public int f(String a, String b) {
            StringBuilder sb=new StringBuilder(b);
            //由于添加单词时索引从小到大，那么节点的idxs必为有序
            List<Integer> s1=t.search(t.root1,a,0);//具有a前缀
            List<Integer> s2=t.search(t.root2,sb.reverse().toString(),0);//具有b后缀
            //从后向前寻找同时存在于两个列表的最大索引
            if(s1!=null&&s2!=null){
                for (int i = s1.size()-1,j=s2.size()-1; i >=0 ; i--) {
                    while(j>=0){
                        if(s2.get(j).equals(s1.get(i)))//Integer类型比较
                            return s1.get(i);
                        if(s2.get(j)<s1.get(i))
                            break;
                        j--;
                    }
                }
            }
            return -1;
        }