745. Prefix and Suffix Search

use Trie

組合的時候: public WordFilter(String[] words)

前面放原單詞的部分, 後面都放完整的, 為什麼這樣做呢？

apple#apple, 'pple#apple', 'ple#apple', 'le#apple', 'e#apple', #apple',

所以 f() 比對時, input 如果是 le#ap (suffix + # + prefix

這樣從前面開始比對, 就會可以比對到 'le#apple'

因為組的時候, 就會變成 sufix和 # 原單詞 的所有組合！！！

T:

WordFilter : O(n*L^2), n is words size, L is each word's len

f:() : O(QL), Q is times of query

S: O(n*L^2)

class WordFilter {
    
    class TrieNode {
        Map<Character, TrieNode> sons;
        int weight;
        TrieNode() {
            this.sons = new HashMap<>();
            this.weight = weight;
        }
    }
    private TrieNode root;
    private void insert(String word, int weight) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            node.sons.putIfAbsent(c, new TrieNode());
            node = node.sons.get(c);
            node.weight = weight;
        }
    }

    public WordFilter(String[] words) {
        root = new TrieNode();
        for (int i = 0; i < words.length; i++) {
            int weight = i;
            
            String word = "{" + words[i];
            insert(word, weight);
            for (int j = 0; j < word.length(); j++) {
                insert(word.substring(j+1) + word, weight);
            }
        }
    }
    
    public int f(String prefix, String suffix) {
        TrieNode node = root;
        for (char c : (suffix + "{" + prefix).toCharArray()) {
            if (node.sons.get(c) == null) {
                return -1;
            } 
            node = node.sons.get(c);
        }
        return node.weight;
    }
}

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

use HashMap

https://leetcode.com/problems/prefix-and-suffix-search/discuss/110044/Three-ways-to-solve-this-problem-in-Java

也可以用 hashmap, 但記憶體應該消耗很兇, 但 f() 非常快：O(1) or O(L), 但在 字串超長時, 應該會 hash conflic 太嚴重而無法作用...

class WordFilter {
    
    private Map<String, Integer> map;
    public WordFilter(String[] words) {
        map = new HashMap<>();
        
        for (int w = 0; w < words.length; w++) {
            int wordLen = words[w].length();
            
            // [0, wordLen], substring parameter can be 0 (entire String)
            // 1 <= words[i].length <= 10, so can have i<=10 this condition
            for (int i = 0; i <= 10 && i <= wordLen; i++) {
                for (int j = 0; j <= 10 && j <= wordLen; j++) {
                    // all prefx + # + all suffix
                    String key = words[w].substring(0, i) + "#" + words[w].substring(wordLen - j);
                    map.put(key, w);
                }
            }
        }
    }
    
    public int f(String prefix, String suffix) {
        String wordKey = prefix + "#" + suffix;
        return map.containsKey(wordKey) ? map.get(wordKey) : -1;
    }
}

/**
 hashmap store all prefx + # + all suffix combination
 
 T: 
 WordFilter: O(nL^2)
 f: O(1) or O(L), if hash conflics too heavy
 
 S: O(nL^2)
 */