Hard

题目描述

设计一个特殊的字典，可以通过前缀和后缀来搜索其中的单词。

实现 WordFilter 类：

  • WordFilter(string[] words) 用字典中的单词数组初始化对象。
  • f(string pref, string suff) 返回字典中具有前缀 pref 和后缀 suff 的单词的索引。如果有多个有效索引，返回其中最大的一个。如果字典中不存在这样的单词，返回 -1。

示例 1：

输入
["WordFilter", "f"]
[[["apple"]], ["a", "e"]]
输出
[null, 0]

解释
WordFilter wordFilter = new WordFilter(["apple"]);
wordFilter.f("a", "e"); // 返回 0，因为索引为 0 的单词前缀是 "a"，后缀是 "e"

约束条件：

  • 1 <= words.length <= 10^4
  • 1 <= words[i].length <= 7
  • 1 <= pref.length, suff.length <= 7
  • words[i]、pref 和 suff 仅由小写英文字母组成
  • 最多调用 f 函数 10^4 次

解题思路

这道题要求设计一个支持前缀和后缀搜索的数据结构。核心思路是将前缀和后缀的匹配问题转化为前缀匹配问题。

解法一：字典树（Trie）+ 组合字符串 关键思想是将每个单词的所有可能的后缀-前缀组合存储到字典树中。具体做法：

  1. 对于单词 “apple”，我们生成组合字符串："{apple", “e{apple”, “le{apple”, “ple{apple”, “pple{apple”, “apple{apple”
  2. 使用特殊字符 ‘{’ 作为分隔符（ASCII码紧跟在 ‘z’ 后面）
  3. 当查询前缀 “app” 和后缀 “le” 时，我们在字典树中搜索 “le{app”

解法二：哈希表暴力 对于每次查询，遍历所有单词检查前缀和后缀匹配。虽然简单但效率较低。

推荐使用字典树解法，因为它在多次查询时具有更好的性能。字典树中每个节点存储权重（索引），确保返回最大的有效索引。

代码实现

class TrieNode {
public:
    TrieNode* children[27];
    int weight;
    
    TrieNode() {
        for (int i = 0; i < 27; i++) {
            children[i] = nullptr;
        }
        weight = -1;
    }
};

class WordFilter {
private:
    TrieNode* root;
    
    void insertWord(const string& word, int index) {
        for (int i = 0; i <= word.length(); i++) {
            TrieNode* cur = root;
            cur->weight = index;
            
            for (int j = i; j < word.length(); j++) {
                int idx = word[j] - 'a';
                if (!cur->children[idx]) {
                    cur->children[idx] = new TrieNode();
                }
                cur = cur->children[idx];
                cur->weight = index;
            }
            
            cur = cur->children[26];
            if (!cur) {
                root->children[26] = new TrieNode();
                cur = root->children[26];
            }
            cur->weight = index;
            
            for (int j = 0; j < word.length(); j++) {
                int idx = word[j] - 'a';
                if (!cur->children[idx]) {
                    cur->children[idx] = new TrieNode();
                }
                cur = cur->children[idx];
                cur->weight = index;
            }
        }
    }
    
public:
    WordFilter(vector<string>& words) {
        root = new TrieNode();
        for (int i = 0; i < words.size(); i++) {
            insertWord(words[i], i);
        }
    }
    
    int f(string pref, string suff) {
        TrieNode* cur = root;
        
        for (char c : suff) {
            int idx = c - 'a';
            if (!cur->children[idx]) return -1;
            cur = cur->children[idx];
        }
        
        if (!cur->children[26]) return -1;
        cur = cur->children[26];
        
        for (char c : pref) {
            int idx = c - 'a';
            if (!cur->children[idx]) return -1;
            cur = cur->children[idx];
        }
        
        return cur->weight;
    }
};

class TrieNode:
    def __init__(self):
        self.children = [None] * 27
        self.weight = -1

class WordFilter:
    def __init__(self, words: List[str]):
        self.root = TrieNode()
        for index, word in enumerate(words):
            self._insert_word(word, index)
    
    def _insert_word(self, word, index):
        for i in range(len(word) + 1):
            cur = self.root
            cur.weight = index
            
            for j in range(i, len(word)):
                idx = ord(word[j]) - ord('a')
                if not cur.children[idx]:
                    cur.children[idx] = TrieNode()
                cur = cur.children[idx]
                cur.weight = index
            
            if not cur.children[26]:
                cur.children[26] = TrieNode()
            cur = cur.children[26]
            cur.weight = index
            
            for j in range(len(word)):
                idx = ord(word[j]) - ord('a')
                if not cur.children[idx]:
                    cur.children[idx] = TrieNode()
                cur = cur.children[idx]
                cur.weight = index

    def f(self, pref: str, suff: str) -> int:
        cur = self.root
        
        for c in suff:
            idx = ord(c) - ord('a')
            if not cur.children[idx]:
                return -1
            cur = cur.children[idx]
        
        if not cur.children[26]:
            return -1
        cur = cur.children[26]
        
        for c in pref:
            idx = ord(c) - ord('a')
            if not cur.children[idx]:
                return -1
            cur = cur.children[idx]
        
        return cur.weight

public class TrieNode {
    public TrieNode[] Children = new TrieNode[27];
    public int Weight = -1;
}

public class WordFilter {
    private TrieNode root;
    
    public WordFilter(string[] words) {
        root = new TrieNode();
        for (int i = 0; i < words.Length; i++) {
            InsertWord(words[i], i);
        }
    }
    
    private void InsertWord(string word, int index) {
        for (int i = 0; i <= word.Length; i++) {
            TrieNode cur = root;
            cur.Weight = index;
            
            for (int j = i; j < word.Length; j++) {
                int idx = word[j] - 'a';
                if (cur.Children[idx] == null) {
                    cur.Children[idx] = new TrieNode();
                }
                cur = cur.Children[idx];
                cur.Weight = index;
            }
            
            if (cur.Children[26] == null) {
                cur.Children[26] = new TrieNode();
            }
            cur = cur.Children[26];
            cur.Weight = index;
            
            for (int j = 0; j < word.Length; j++) {
                int idx = word[j] - 'a';
                if (cur.Children[idx] == null) {
                    cur.Children[idx] = new TrieNode();
                }
                cur = cur.Children[idx];
                cur.Weight = index;
            }
        }
    }
    
    public int F(string pref, string suff) {
        TrieNode cur = root;
        
        foreach (char c in suff) {
            int idx = c - 'a';
            if (cur.Children[idx] == null) return -1;
            cur = cur.Children[idx];
        }
        
        if (cur.Children[26] == null) return -1;
        cur = cur.Children[26];
        
        foreach (char c in pref) {
            int idx = c - 'a';
            if (cur.Children[idx] == null) return -1;
            cur = cur.Children[idx];
        }
        
        return cur.Weight;
    }
}

class TrieNode {
    constructor() {
        this.children = new Array(27).fill(null);
        this.weight = -1;
    }
}

var WordFilter = function(words) {
    this.root = new TrieNode();
    for (let i = 0; i < words.length; i++) {
        this.insertWord(words[i], i);
    }
};

WordFilter.prototype.insertWord = function(word, index) {
    for (let i = 0; i <= word.length; i++) {
        let cur = this.root;
        cur.weight = index;
        
        for (let j = i; j < word.length; j++) {
            let idx = word.charCodeAt(j) - 97;
            if (!cur.children[idx]) {
                cur.children[idx] = new TrieNode();
            }
            cur = cur.children[idx];
            cur.weight = index;
        }
        
        if (!cur.children[26]) {
            cur.children[26] = new TrieNode();
        }
        cur = cur.children[26];
        cur.weight = index;
        
        for (let j = 0; j < word.length; j++) {
            let idx = word.charCodeAt(j) - 97;
            if (!cur.children[idx]) {
                cur.children[idx] = new TrieNode();
            }
            cur = cur.children[idx];
            cur.weight = index;
        }
    }
};

WordFilter.prototype.f = function(pref, suff) {
    let cur = this.root;
    
    for (let c of suff) {
        let idx = c.charCodeAt(0) - 97;
        if (!cur.children[idx]) return -1;
        cur = cur.children[idx];
    }
    
    if (!cur.children[26]) return -1;
    cur = cur.children[26];
    
    for (let c of pref) {
        let idx = c.charCodeAt(0) - 97;
        if (!cur.children[idx]) return -1;
        cur = cur.children[idx];
    }
    
    return cur.weight;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度字典树解法
时间复杂度构造：O(N × L²)，查询：O(P + S)
空间复杂度O(N × L²)

其中 N 为单词数量，L 为单词平均长度，P 为前缀长度，S 为后缀长度。

相关题目