力扣：745. 前缀和后缀搜索

import java.util.HashMap;
import java.util.Map;


public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        WordFilter2 wordFilter = new WordFilter2(new String[]{"apple"});
        wordFilter.f("a", "le");
    }


}


class WordFilter {
    Map map;
    public WordFilter(String[] words) {
        map = new HashMap<>();
        for (int k = 0; k < words.length; k++) {
            String word = words[k];
            int m = word.length();
            for (int i = 1; i <= m; i++){
                for (int j = 1; j <= m; j++){
                    map.put(word.substring(0, i) + "#" + word.substring(m - j), k);
                }
            }
        }
    }

    public int f(String pref, String suff) {
        return map.getOrDefault(pref + "#" + suff, -1);
    }
}


class WordFilter2 {

    class Trie{
        Map children;
        Map weight;
        public Trie(){
            children = new HashMap<>();
            weight = new HashMap<>();
        }
    }

    Trie trie;
    String weightKey;
    public WordFilter2(String[] words) {
        trie = new Trie();
        weightKey = "##";
        for (int i = 0; i < words.length; i++){
            String word = words[i];
            Trie cur = trie;
            int m = word.length();
            for (int j = 0; j < m; j++){
                Trie tmp = cur;
                for (int k = j; k < m; k++){
                    String key = word.charAt(k) + "#";
                    if (!tmp.children.containsKey(key)){
                        tmp.children.put(key, new Trie());
                    }
                    tmp = tmp.children.get(key);
                    tmp.weight.put(weightKey, i);
                }
                tmp = cur;
                for (int k = j; k < m; k++){
                    String key = "#" + word.charAt(m - k - 1);
                    if (!tmp.children.containsKey(key)){
                        tmp.children.put(key, new Trie());
                    }
                    tmp = tmp.children.get(key);
                    tmp.weight.put(weightKey, i);
                }
                String key = new StringBuilder().append(word.charAt(j)).append( word.charAt(m - j - 1)).toString();
                if (!cur.children.containsKey(key)){
                    cur.children.put(key, new Trie());
                }
                cur = cur.children.get(key);
                cur.weight.put(weightKey, i);
            }
        }
    }

    public int f(String pref, String suff) {
        Trie cur = trie;
        int m = Math.max(pref.length(), suff.length());
        for (int i = 0; i < m; i++){
            char c1 = i < pref.length() ? pref.charAt(i) : '#';
            char c2 = i < suff.length() ? suff.charAt(suff.length() - 1 - i) : '#';
            String key = new StringBuilder().append(c1).append(c2).toString();
            if (!cur.children.containsKey(key)){
                return  - 1;
            }
            cur = cur.children.get(key);
        }
        return cur.weight.get(weightKey);
    }
}