首页 > 编程学习 > 【Leetcode】745. Prefix and Suffix Search

【Leetcode】745. Prefix and Suffix Search

发布时间:2022/11/5 19:59:54

题目地址:

https://leetcode.com/problems/prefix-and-suffix-search/description/

要求实现一个数据结构,可以做如下操作:
1、以一个只含英文小写字母单词的列表初始化;
2、给定一个前缀和后缀,返回列表中以这个前缀为前缀、以这个后缀为后缀的单词的下标。如果有多个单词满足条件,则返回下标最大的那个。

对于每个给定的长 n n n的单词 s s s,我们可以将 s s s的逆序的所有前缀加上一个特殊符号例如#,再加上 s s s本身,这 n n n个字符串插入一个Trie中。这样,如果某个单词的查询结果是 s s s,设要查询的前缀是 p p p,后缀是 q q q,则我们去查 q + # + p q+\#+p q+#+p,这个字符串一定在Trie的 s s s的路径上。反之,也成立。所以我们只需要将每个节点的经过其的所有路径的字符串的下标最大值存起来,查询的时候只需要查到终点看一下那个权值即可。代码如下:

class WordFilter {
 public:
  struct Node {
    int w;
    Node* ne[27];
    Node() : w(-1) { fill(ne, ne + 27, nullptr); }
  };

  Node* root;

  void insert(string& s, int id) {
    auto p = root;
    for (auto ch : s) {
      int c = ch != '#' ? ch - 'a' : 26;
      if (!p->ne[c]) p->ne[c] = new Node();
      p = p->ne[c];
      p->w = id;
    }
  }

  WordFilter(vector<string>& words) {
    root = new Node();
    for (int i = 0; i < words.size(); i++) {
      string s = "#" + words[i];
      insert(s, i);
      for (int j = words[i].size() - 1; j >= 0; j--) {
        s = words[i][j] + s;
        insert(s, i);
      }
    }
  }

  int f(string pref, string suff) {
    string s = suff + "#" + pref;
    auto p = root;
    for (auto ch : s) {
      int c = ch != '#' ? ch - 'a' : 26;
      if (!p->ne[c]) return -1;
      p = p->ne[c];
    }

    return p->w;
  }
};

初始化时间复杂度 O ( ∑ i l s i 2 ) O(\sum_i l^2_{s_i}) O(ilsi2),每次询问时间复杂度 O ( l s ) O(l_s) O(ls)

Copyright © 2010-2022 dgrt.cn 版权所有 |关于我们| 联系方式