本文共 2995 字，大约阅读时间需要 9 分钟。

为了有效解决问题，我们将使用前缀树和后缀树 结合技巧来实现快速查询。以下是详细的解决方法：

方法思路

为了高效找到具有给定前缀和后缀的单词，并且具有最大权重，我们可以使用前缀树和后缀树进行插入，然后针对每个查询分别处理。

这种方法确保了插入和查询的效率，分别为O(n * m)和O(m)，其中n是单词长度，m是查询时间复杂度。

解决代码

以下是实现用C++的代码：

#include 
   
    #include 
    
     #include 
     
      using namespace std;struct TrieNode {    vector
      
        last;    TrieNode* next[26];    bool isEnd;    TrieNode() : isEnd(false), last(0) {        for (int i = 0; i < 26; ++i) {            next[i] = NULL;        }    }};class TrieTree {public:    TrieTree() {        root = new TrieNode();    }    void insert(const string& word, int index) {        TrieNode* current = root;        current->last.push_back(index);        for (int i = 0; i < word.size(); ++i) {            int c = word[i] - 'a';            if (current->next[c] == NULL) {                current->next[c] = new TrieNode();            }            current = current->next[c];            current->last.push_back(index);        }        current->isEnd = true;    }    void rinsert(const string& word, int index) {        TrieNode* current = root;        current->last.push_back(index);        for (int i = word.size() - 1; i >= 0; --i) {            int c = word[i] - 'a';            if (current->next[c] == NULL) {                current->next[c] = new TrieNode();            }            current = current->next[c];            current->last.push_back(index);        }        current->isEnd = true;    }    vector
       
         startWith(const string& prefix) {        TrieNode* current = root;        for (int i = 0; i < prefix.size(); ++i) {            int c = prefix[i] - 'a';            if (current->next[c] == NULL) {                return vector
        
         (); } current = current->next[c]; } return current->last; }private: TrieNode* root;};class WordFilter {public: WordFilter(vector
         
           words) { for (int i = 0; i < words.size(); ++i) { tree.insert(words[i], i); rtree.rinsert(words[i], i); } } int f(string prefix, string suffix) { vector
          
            pre = tree.startWith(prefix); if (pre.empty()) { return -1; } string reversedSuffix = string(suffix.rbegin(), suffix.rend()); vector
           
             suf = rtree.startWith(reversedSuffix); if (suf.empty()) { return -1; } int maxIndex = -1; int i = pre.size() - 1, j = suf.size() - 1; while (i >= 0 && j >= 0) { if (pre[i] == suf[j]) { if (pre[i] > maxIndex) { maxIndex = pre[i]; } --j; } else if (pre[i] < suf[j]) { --i; } else { break; } } return maxIndex != -1 ? maxIndex : -1; }private: TrieTree tree; TrieTree rtree;};
           
          
         
        
       
      
     
    
   

代码解释

该实现确保了插入和查询的效率，能够在大输入规模下高效运行。通过将每个单词的前缀和后缀分别存储在不同的树中，能够快速筛选出满足条件的单词，并因为每个树的查询复杂度为O(m)，整体性能得到优化。