LeetCode 745. 前缀和后缀搜索

745. 前缀和后缀搜索

【哈希+打表】首先这是个一次构造多次查询的问题，而且words数组的长度只有10^ 4，并且每个word的长度只有7，那么以每个单词前缀后缀组成的单词总数一共有6 * 6 * 10 ^ 4种，可以把他存在哈希表中，然后来了前后缀直接组合起来查表就行了。

class WordFilter {

    // 哈希+打表

    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);
 */

【字典树TLE版】建一个前缀字典树和一个后缀字典树，只不过end标记用来存下标了。但是当查找前缀时，这里有一个bfs，本质上还是爆搜，所以TLE了。

class WordFilter {

    // 字典树 3:11 30
    // 写一个前缀字典树再写一个后缀字典树吧。。

    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一下
            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);
 */

【字典树改进】但是我们发现建树的时候其实可以把单词走过的节点都留下痕迹，也就是说这里end不再只是存一个下标了，然后用list把所有经过了他的单词下标都存下来。

class WordFilter {

    // 带路径字典树 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);
 */

注意Integer封装类型比较想等不能用==，得用equals方法。