【面试高频题难度 3/5，字典树热门运用题

题目描述

这是 LeetCode 上的 745. 前缀和后缀搜索 ，难度为 困难。

Tag : 「字典树」

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

实现 WordFilter 类：

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

示例：

输入
["WordFilter", "f"]
[[["apple"]], ["a", "e"]]

输出
[null, 0]

解释
WordFilter wordFilter = new WordFilter(["apple"]);
wordFilter.f("a", "e"); // 返回 0 ，因为下标为 0 的单词：前缀 prefix = "a" 且 后缀 suff = "e" 。

提示：

• 1tns[u];
  p->idxs.push_back(idx);
  }
  }

  int query(const string& a, const string& b) {
  int n = a.size(), m = b.size();
  auto p = tr1;
  for(int i = 0; i tns[u] == nullptr) return -1;
  p = p->tns[u];
  }
  vector& l1 = p->idxs;
  p = tr2;
  for(int i = m - 1; i >= 0; i--) {
  int u = b[i] - 'a';
  if(p->tns[u] == nullptr) return -1;
  p = p->tns[u];
  }
  vector& l2 = p->idxs;
  n = l1.size(), m = l2.size();
  for(int i = n - 1, j = m - 1; i >= 0 && j >= 0; ) {
  if(l1[i] > l2[j]) i--;
  else if(l1[i] < l2[j]) j--;
  else return l1[i];
  }
  return -1;
  }

  TrieNode* tr1 = new TrieNode, *tr2 = new TrieNode;
  WordFilter(vector& ss) {
  int n = ss.size();
  for(int i = 0; i < n; i++) {
  add(tr1, ss[i], i, false);
  add(tr2, ss[i], i, true);
  }
  }

  int f(string a, string b) {
  return query(a, b);
  }
  };
  

  • 时间复杂度：初始化操作复杂度为 O(∑i=0n−1ss[i].length)O(\sum_{i = 0}^{n - 1} ss[i].length)O(∑i=0n−1​ss[i].length)，检索过程复杂度为 O(a+b+n)O(a + b + n)O(a+b+n)，其中 a=b=7a = b = 7a=b=7 为前后缀的最大长度，n=1e4n = 1e4n=1e4 为初始化数组长度，代表最多有 nnn 个候选下标（注意：这里的 nnn 只是粗略分析，实际上如果候选集长度越大的话，说明两个候选集是重合度是越高的，从后往前找的过程是越快结束的，可以通过方程算出一个双指针的理论最大比较次数 kkk，如果要将 nnn 卡满成 1e41e41e4 的话，需要将两个候选集设计成交替下标，此时 f 如果仍是 1e41e41e4 次调用的话，必然会面临大量的重复查询，可通过引入 map 记录查询次数来进行优化）
  • 空间复杂度：O(∑i=0n−1ss[i].length)O(\sum_{i = 0}^{n - 1} ss[i].length)O(∑i=0n−1​ss[i].length)

  最后

  这是我们「刷穿 LeetCode」系列文章的第 No.745 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

  在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

  为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。

  在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

  更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉