LeetCode 745. Prefix and suffix search

745. Prefix and suffix search

【 Hash + The meter 】 First of all, this is a problem of constructing multiple queries at one time , and words The length of the array is only 10^ 4, And each word The length of is only 7, Then the total number of words composed of prefixes and suffixes of each word is 6 * 6 * 10 ^ 4 Kind of , You can save it in the hash table , Then, when the prefix comes, you can directly combine it to look up the table .

class WordFilter {

    //  Hash + The meter 

    Map<String, Integer> map = new HashMap();

    public WordFilter(String[] words) {
        int k = 0;
        for (var str: words) {
            var n = str.length();
            for (var i = 1; i <= n; i++) {
                for (var j = 0; j < n; j++) {
                    map.put(str.substring(0, i) + "#" + str.substring(j, n), k);
                }
            }
            k++;
        }
    }
    
    public int f(String pref, String suff) {
        return map.getOrDefault(pref + "#" + suff, -1);
    }
}

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

【 Dictionary tree TLE edition 】 Build a prefix dictionary tree and a suffix dictionary tree , It's just end Tags are used to save subscripts . But when looking for prefixes , Here's one bfs, In essence, it is still explosive search , therefore TLE 了 .

class WordFilter {

    //  Dictionary tree  3:11 30
    //  Write a prefix dictionary tree and a suffix dictionary tree ..

    class Trie {
        Trie[] map = new Trie[26];
        int end = -1;
    }

    Trie pre = new Trie();
    Trie suf = new Trie();

    void add(String str, boolean reverse, int num) {
        if (!reverse) {
            Trie node = pre;
            for (var i = 0; i < str.length(); i++) {
                int idx = str.charAt(i) - 'a';
                if (node.map[idx] == null) {
                    Trie trie = new Trie();
                    node.map[idx] = trie;
                }
                node = node.map[idx];
            }
            node.end = num;
        } else {
            Trie node = suf;
            for (var i = str.length() - 1; i >= 0; i--) {
                int idx = str.charAt(i) - 'a';
                if (node.map[idx] == null) {
                    Trie trie = new Trie();
                    node.map[idx] = trie;
                }
                node = node.map[idx];
            }
            node.end = num;
        }
    }

    Set<Integer> search(String str, boolean reverse) {
        Set<Integer> set = new HashSet();
        if (!reverse) {
            Trie node = pre;
            for (var i = 0; i < str.length(); i++) {
                int idx = str.charAt(i) - 'a';
                if (node.map[idx] == null) return set;
                node = node.map[idx];
            }
            // bfs once 
            Queue<Trie> queue = new LinkedList();
            queue.offer(node);
            while (!queue.isEmpty()) {
                Trie top = queue.poll();
                if (top.end != -1) set.add(top.end);
                for (var i = 0; i < 26; i++) {
                    if (top.map[i] != null) queue.offer(top.map[i]);
                }
            }
            return set;
        } else {
            Trie node = suf;
            for (var i = str.length() - 1; i >= 0; i--) {
                int idx = str.charAt(i) - 'a';
                if (node.map[idx] == null) return set;
                node = node.map[idx];    
            }
            Queue<Trie> queue = new LinkedList();
            queue.offer(node);
            while (!queue.isEmpty()) {
                Trie top = queue.poll();
                if (top.end != -1) set.add(top.end);
                for (var i = 0; i < 26; i++) {
                    if (top.map[i] != null) queue.offer(top.map[i]);
                }
            }
            return set;
        }
    }

    public WordFilter(String[] words) {
        for (var i = 0; i < words.length; i++) {
            add(words[i], false, i);
            add(words[i], true, i);
        }
    }
    
    public int f(String pref, String suff) {
        Set<Integer> s1 = search(pref, false);
        Set<Integer> s2 = search(suff, true);
        s1.retainAll(s2);
        int ans = -1;
        for (var i: s1) ans = Math.max(ans, i);
        return ans;
    }
}

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

【 Dictionary tree improvement 】 But we found that when building a tree, we can actually leave traces of the nodes the words have passed , That is to say, here end No longer just save a subscript , And then use list Save all the subscripts of the words that have passed him .

class WordFilter {

    //  Dictionary tree with path  4:06 60

    class Trie {
        Trie[] map = new Trie[26];
        List<Integer> end = new ArrayList();
    }

    Trie pre = new Trie(), suf = new Trie();

    void add(String str, boolean reverse, int idx) {
        int start = 0, t = 1;
        Trie node = pre;
        if (reverse) {
            start = str.length() - 1;
            t = -1;
            node = suf;
        }
        for (var i = start; i >=0 && i < str.length(); i += t) {
            var j = str.charAt(i) - 'a';
            if (node.map[j] == null) {
                node.map[j] = new Trie();
            }
            node = node.map[j];
            node.end.add(idx);
        }
    }

    List<Integer> search(String str, boolean reverse) {
        int start = 0, t = 1;
        Trie node = pre;
        if (reverse) {
            start = str.length() - 1;
            t = -1;
            node = suf;
        }
        for (var i = start; i >= 0 && i < str.length(); i += t) {
            var j = str.charAt(i) - 'a';
            if (node.map[j] == null) return new ArrayList();
            node = node.map[j];
        }
        return node.end;
    }

    public WordFilter(String[] words) {
        for (var i = 0; i < words.length; i++) {
            add(words[i], true, i);
            add(words[i], false, i);
        }
    }
    
    public int f(String pref, String suff) {
        List<Integer> l1 = search(pref, false);
        List<Integer> l2 = search(suff, true);
        int i = l1.size() - 1, j = l2.size() - 1;
        while (i >= 0 && j >= 0) {
            // System.out.println(l1.get(i) + " " + l2.get(j));
            if (l1.get(i).equals(l2.get(j))) return l1.get(i);
            else if (l1.get(i) < l2.get(j)) j--;
            else i--;
        }
        return -1;
    }
}

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

Be careful Integer The package type is too hard to use ==, Have to use equals Method .