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