Leetcode.745. prefix and suffix search____ Double dictionary tree + double pointer

745. Prefix and suffix search

Design a special dictionary that contains some words , And can retrieve words through prefixes and suffixes .

Realization WordFilter class ：

WordFilter(string[] words) Use words in the dictionary words Initialize object .
f(string pref, string suff) The return dictionary has a prefix prefix And suffixes suff The subscript of the word . If there is more than one subscript that meets the requirements , Return to it The largest subscript . If there is no such word , return -1 .

Example ：

Input
[“WordFilter”, “f”]
[[[“apple”]], [“a”, “e”]]
Output
[null, 0]
explain
WordFilter wordFilter = new WordFilter([“apple”]);
wordFilter.f(“a”, “e”); // return 0 , Because the index is zero 0 's words ： Prefix prefix = “a” And suffix suff = “e” .

Tips ：

• 1 <= words.length <= 104
• 1 <= words[i].length <= 7
• 1 <= pref.length, suff.length <= 7
• words[i]、pref and suff It's only made up of lowercase letters
• Up to function f perform 104 Secondary call

Solution:

It is mainly difficult to query at the same time , If it's just a prefix, we can go directly through the dictionary tree startwith The query , But for suffixes, we find that we can't deal with them directly , So we can think negatively , Start from the opposite side , That is, when we save words into the dictionary tree , If all are stored in reverse order , Then we have suffixes in the query suff When the word is , You can find suff Take the word with the inverse as the prefix , Therefore, the unified problem is to find the prefix .

• We can implement two dictionary trees ,A Store directly and normally words,B take words The words inside are inverted and stored , And each dictionary tree node additionally records that the current node is words Which subscripts of are used by the corresponding elements .
• thus , about A, We use the dictionary tree directly startwith Method query prefix, Make it return to the last queried node , So we can get words String array with prefix Subscript the prefixed element ; about B, We also use the dictionary tree directly startwith Method to query suff, Just will suff Take the negative to change to the search prefix .
• Found with prefix Subscript the prefixed element with suff After subscript the suffix element , We can use double pointers to compare from the maximum subscript , Whoever is older can lower .

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);  
         //  Originally, when inserting this and the eighth line into the dictionary tree, you need to reverse the string to insert , Now turn the search rule directly into the reverse, so the previous one doesn't need to be written 
        if(list1 == null || list2 == null){
    
            return -1;
        }
        
        /*  Double pointer  */
        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--;
            }
        } 

        /*  Hash  */
        // 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();
        //  Open up more method space , In this way, the previous string does not need to be inversed , Insert directly in reverse order 
        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();
        //  Same as insert2 How to deal with it 
        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];   //  It seems that it is directly opened 26 Pit , But in fact, there are no pits new, So there is no data , So it's just fake , Just put 26 A point opened ,
                                    //  Only the elements that really exist in a certain direction can be really opened 
            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); */