Leetcode 745 搜索带有前缀和后缀的字符串

题目描述

搜索带有前缀和后缀的字符串

样例

比如字典里面有apple，而且apple在字典里面的位置为0。 那么如果搜"a", "e"（前缀是a，后缀是e）的结果就应该是0。这道题有两种解法，一种是直接用hashmap，把每个单词的前缀
和后缀的方式都存进哈希表里。
另一种方法是利用前缀树的特点，把每个插入的单词的后缀都存进Trie里，并且加入一个"{"符号，因为"{"正好在ascii码上面是z的后一位(参考http://www.asciitable.com/)。这样就可以建一个27位子树的Trie了，每次搜索就直接搜后缀+“{"+整个前缀，（这里因为我们插入的时候把每个node的id都设置成了该字符串的id，所以只要搜索到前缀的最后一个字母就可以直接返回当前节点的id了

参考文献

lc 答案和讨论区
https://leetcode.com/problems/prefix-and-suffix-search/discuss/110044/Three-ways-to-solve-this-problem-in-Java

算法1

Hashmap L是每个单词长度

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

    public int f(String prefix, String suffix) {
        return (map.containsKey(prefix + "#" + suffix)) ? map.get(prefix + "#" + suffix) : -1;
    }
}

算法2

普通Trie L 是每个字符串的长度

插入的时候直接把每种后缀可能枚举一遍并加上“{" 和整个单词，这样前缀和的所有可能也全包括了，当然这样就比较浪费空间。

class WordFilter {
  Trie trie = new Trie();
  public WordFilter(String[] words) {
    for (int i = 0; i < words.length; i++) {
      for (int j = 0; j < words[i].length(); j++) {
        String cur = words[i];
        trie.insert(cur.substring(j, cur.length()) + "{" + cur, i);
      }
    }
  }

  public int f(String prefix, String suffix) {
    return trie.search(suffix + "{" + prefix);
  }
}
class Trie {
  TrieNode root;
  public Trie() {
    root = new TrieNode();
  }
  public void insert(String s, int num) {
    TrieNode node = root;
    for (int i = 0; i < s.length(); i++) {
      char c = s.charAt(i);
      if (node.children[c - 'a'] == null) node.children[c - 'a'] = new TrieNode();
      node = node.children[c - 'a'];
      node.id = num;
    }
  }

  public int search(String prefix) {
    TrieNode node = root;
    for (int i = 0; i < prefix.length(); i++) {
      char c = prefix.charAt(i);
      if (node.children[c - 'a'] == null) return -1;
      node = node.children[c - 'a'];
    }
    return node.id;
  }
}

class TrieNode {
  TrieNode[] children;
  int id;
  public TrieNode() {
    children = new TrieNode[27];
  }
}