题目描述

给定单词列表 words, 其中words[i] 的权重是 i.

设计一个类 WordFilter,支持查询函数 WordFilter.f(String prefix, String suffix).该查询函数返回给定前缀和后缀的权重最大的单词的权重.如果不存在,则返回-1

样例

Input:
WordFilter(["apple"])
WordFilter.f("a", "e") // returns 0
WordFilter.f("b", "") // returns -1

算法1

(线段树构造) $O(NK^2 + QK)$

我们对每个单词的所有后缀,拼接上’#’,在拼接上原单词.把整个字符串插入到线段树中.

以apple为例,我们会插入 ‘#apple’, ‘e#apple’, ‘le#apple’, ‘ple#apple’, ‘pple#apple’, ‘apple#apple’ 到线段树中. 如果查询前缀是 “ap”,后缀是”le”的单词,我们可以够着这样的查询语句 “le#ap”.

时间复杂度分析：$O(NK^2 + QK)$
$N$ 是单词个数
$K$ 是单词的最大长度
$Q$ 是查询数量

空间复杂度分析: $O(NK^2)$, 线段树的空间

C++ 代码

class Trie{
  public:
    Trie * _children[27];
    int id;
    Trie(){
      for(int i=0;i<27;i++){
        this->_children[i]=nullptr;
      }
      this->id=-1;
    }
    void insert(string,int);
    int query(string);
};

void Trie::insert(string s,int id){
  Trie* curr=this;
  int j;
  for(char c:s){
    Trie * t;
    if(c=='#'){j=26;}else{ j=c-'a'; }
    if(!curr->_children[j]){
      curr->_children[j]=new Trie();
    }
    curr->id=id;
    curr=curr->_children[j];
  }
  curr->id=id;
}

int Trie::query(string s){
  Trie* curr=this;
  int j;
  for(char c:s){
    if(c=='#'){j=26;}else{ j=c-'a'; }
    if(!curr->_children[j]){return -1;}
    curr=curr->_children[j];
  }
  return curr->id;
}

class WordFilter {
  public:
    Trie * prefixTrie;
    int N;

    WordFilter(vector<string>& words) {
      N=words.size();
      prefixTrie=new Trie();

      for(int i=0;i<N;i++){
        string word="#"+words[i];
        prefixTrie->insert(word,i);
        for(int j=1;j<word.size();j++){
          string temp=word.substr(j)+word;
          prefixTrie->insert(temp,i);
        }
      }
    }

    int f(string prefix, string suffix) {
      string s=suffix+"#"+prefix;
      return prefixTrie->query(s);
    }

};