LeetCode.745. 前缀和后缀搜索____双字典树+双指针

745. 前缀和后缀搜索

设计一个包含一些单词的特殊词典，并能够通过前缀和后缀来检索单词。

实现 WordFilter 类：

WordFilter(string[] words) 使用词典中的单词 words 初始化对象。
f(string pref, string suff) 返回词典中具有前缀 prefix 和后缀 suff 的单词的下标。如果存在不止一个满足要求的下标，返回其中 最大的下标 。如果不存在这样的单词，返回 -1 。

示例：

输入
[“WordFilter”, “f”]
[[[“apple”]], [“a”, “e”]]
输出
[null, 0]
解释
WordFilter wordFilter = new WordFilter([“apple”]);
wordFilter.f(“a”, “e”); // 返回 0 ，因为下标为 0 的单词：前缀 prefix = “a” 且 后缀 suff = “e” 。

提示：

• 1 <= words.length <= 104
• 1 <= words[i].length <= 7
• 1 <= pref.length, suff.length <= 7
• words[i]、pref 和 suff 仅由小写英文字母组成
• 最多对函数 f 执行 104 次调用

Solution:

这里主要是难在前后缀同时要查询，如果只是前缀我们可以直接通过字典树的startwith进行查询，但是对于后缀我们发现无法直接处理，所以我们可以反面思考，从反面出发，即我们在将单词存进字典树时，如果全部倒序存储，那么我们在查询有后缀suff的单词时，即可变为查找suff取反后作为前缀的单词即可，因此可统一问题为查找前缀。

• 我们可以实现两个字典树，A直接正常存放words，B将words的单词内部颠倒后进行存储，且每一个字典树节点都额外记录一下当前节点被words的哪几个下标对应的元素所使用。
• 这样一来，对于A，我们直接使用字典树的startwith方法查询prefix，使其返回最后查询到的节点即可，这样我们即可得到words字符串数组中以prefix为前缀的元素下标；对于B，我们也是直接用字典树的startwith方法进行查询suff，只不过将suff取反即可变为查找前缀。
• 查找到以prefix为前缀的元素下标和以suff为后缀的元素下标后，我们就可以使用双指针从最大下标进行比对，谁大谁就降低即可。

Code:

class WordFilter {
    
    private Node a;
    private Node b;

    public WordFilter(String[] words) {
    
        a = new Node();
        b = new Node();
        int len = words.length;
        for(int i=0;i<len;i++){
    
            insert1(a,words[i],i);
            insert2(b,words[i],i);
        }
    }
    
    public int f(String pref, String suff) {
    
        List<Integer> list1 = startsWith1(a,pref);
        List<Integer> list2 = startsWith2(b,suff);  
         // 本来是这个和第八行插入字典树的时候都需要将字符串反转进行插入，现在直接将查找的规则变成反过来所以前面的就不用写了
        if(list1 == null || list2 == null){
    
            return -1;
        }
        
        /* 双指针 */
        int i = list1.size() - 1;
        int j = list2.size() - 1;

        while(i >= 0 && j >= 0){
    
            int index1 = list1.get(i);
            int index2 = list2.get(j);

            if(index1 == index2){
    
                return index1;
            }
            else if(index1 > index2){
    
                index1--;
            }
            else{
    
                index2--;
            }
        } 

        /* 哈希 */
        // int[] hash = new int[10001];
        // for(Integer one : list1)
        // hash[one]++;

        // for(Integer one : list2)
        // hash[one]++;

        // for(int i=10000;i>=0;i--){
    
        // if(hash[i] == 2){
    
        // return i;
        // }
        // } 

        return -1;
    }

    public void insert1(Node a,String word,int index){
    
        Node temp = a;
        char[] array = word.toCharArray();
        for(int i=0;i<array.length;i++){
    
            char c = array[i];
            if(temp.contains(c)){
    
                temp = temp.get(c);
                temp.list.add(index);
            }
            else{
    
                temp.put(c);
                temp = temp.get(c);
                temp.list.add(index);
            }
        }
    }

    public void insert2(Node b,String word,int index){
    
        Node temp = b;
        char[] array = word.toCharArray();
        // 多开辟方法空间，这样前面字符串就不用额外的进行取反了，直接倒序插入
        for(int i=array.length - 1;i >= 0;i--){
    
            char c = array[i];
            if(temp.contains(c)){
    
                temp = temp.get(c);
                temp.list.add(index);
            }
            else{
    
                temp.put(c);
                temp = temp.get(c);
                temp.list.add(index);
            }
        }
    }

    public List<Integer> startsWith1(Node a,String prefix){
    
        Node temp = a;
        char[] array = prefix.toCharArray();
        for(int i=0;i<array.length;i++){
    
            char c = array[i];
            if(temp.contains(c)){
    
                temp = temp.get(c);
            }
            else{
    
                return null; 
            }
        }
        return temp.list;
    }

    public List<Integer> startsWith2(Node b,String suff){
    
        Node temp = b;
        char[] array = suff.toCharArray();
        // 同insert2的处理思想
        for(int i=array.length - 1;i >= 0;i--){
    
            char c = array[i];
            if(temp.contains(c)){
    
                temp = temp.get(c);
            }
            else{
    
                return null; 
            }
        }
        return temp.list;
    }

    private class Node{
    
        Node[] nodes;
        List<Integer> list;

        public Node(){
    
            nodes = new Node[26];   // 看样子是直接开了26个坑，但是其实由于每一个坑都没有new，所以都没数据，所以其实只是假开，只是把26个指向开了，
                                    // 后面只有真正存在某个方向的元素才会真开
            list = new ArrayList<>();
        }

        public boolean contains(char key){
    
            if(nodes[key - 'a'] != null)
                return true;
            return false;
        }

        public Node get(char key){
    
            return nodes[key - 'a'];
        }  

        public void put(char key){
    
            nodes[key - 'a'] = new Node();
        }
    }
}

/** * Your WordFilter object will be instantiated and called as such: * WordFilter obj = new WordFilter(words); * int param_1 = obj.f(pref,suff); */