题目

题目来源：力扣（LeetCode）

设计一个包含一些单词的特殊词典，并能够通过前缀和后缀来检索单词。

实现 WordFilter 类：

WordFilter(string[] words) 使用词典中的单词 words 初始化对象。
f(string prefix, string suffix) 返回词典中具有前缀 prefix 和后缀suffix 的单词的下标。如果存在不止一个满足要求的下标，返回其中 最大的下标 。如果不存在这样的单词，返回 -1 。

示例

输入：
[“WordFilter”, “f”]
[[[“apple”]], [“a”, “e”]]
输出：
[null, 0]

解释：
WordFilter wordFilter = new WordFilter([“apple”]);
wordFilter.f(“a”, “e”); // 返回 0 ，因为下标为 0 的单词的 prefix = “a” 且 suffix = ‘e” 。

思路分析

方法：后缀树+前缀树

  1. 往Trie树插入单词时，单词本身包含所有的前缀组合。那么考虑将所有的后缀组合提前，再加一个 特殊字符，组成 后缀+特殊字符+单词 的结构，如 suffix+’#’+word 。那么调用f() 时，只需要查询 suffix+’#’+word 的权重即可。

  2. 对于 apple 这个单词，我们可以在单词查找树插入每个后缀，后跟 “#” 和单词。 例如，我们将在单词查找树中插入 ‘#apple’, ‘e#apple’, ‘le#apple’, ‘ple#apple’, ‘pple#apple’, ‘apple#apple’。然后对于 prefix = “ap”, suffix = “le” 这样的查询，我们可以通过查询单词查找树 找到 le#ap

  1. function TrieNode() {
  2.   this.next = new Map();
  3.   this.weight = 0; //权重，对应单词下标
  4. }
  5. function Trie() {
  6.   // 初始化根节点
  7.   this.root = new TrieNode();
  8. }
  10. // 插入单词
  11. Trie.prototype.insert = function (word, weight) {
  12.   if (!word) return;
  13.   let node = this.root;
  14.   for (let c of word) {
  15.     if (!node.next.has(c)) {
  16.       node.next.set(c, new TrieNode());
  17.     }
  18.     node = node.next.get(c);
  19.     node.weight = weight; // 更新weight
  20.   }
  21. };
  23. /**
  24.  * @param {string[]} words
  25.  */
  26. var WordFilter = function (words) {
  27.   this.tree = new Trie();
  28.   for (let weight = 0; weight < words.length; weight++) {
  29.     let word = words[weight];
  30.     let suffix = '';
  31.     for (let i = word.length; i >= 0; i--) {
  32.       // 单词的后缀
  33.       suffix = word.slice(i, word.length);
  34.       // 把「后缀 + 特殊字符 + 单词」插入字典树
  35.       this.tree.insert(suffix + '#' + word, weight);
  36.     }
  37.   }
  38. };
  39. /**
  40. * @param {string} prefix
  41. * @param {string} suffix
  42. * @return {number}
  43. */
  44. WordFilter.prototype.f = function (prefix, suffix) {
  45.   let target = suffix + '#' + prefix;
  46.   let node = this.tree.root;
  47.   for (let c of target) {
  48.     if (!node.next.has(c)) return -1;
  49.     node = node.next.get(c);
  50.   }
  51.   return node.weight;
  52. };
  54. /**
  55.  * Your WordFilter object will be instantiated and called as such:
  56.  * var obj = new WordFilter(words)
  57.  * var param_1 = obj.f(prefix,suffix)
  58.  */