LeetCode745. 前缀和后缀搜索

题目描述

本题目来自LeetCode上的『745. 前缀和后缀搜索』

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

实现 WordFilter 类：

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

示例1：

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

提示

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

题解1 - 暴力哈希

枚举每个单词所有可能的前缀后缀组合，前缀和后缀之间以 $#$ 分割，并将其对应的下标保存到哈希表中。每次 f() 操作之间从哈希表中查询即可。

代码

class WordFilter {
private:
    unordered_map<string, int> mp;
public:
    WordFilter(vector<string>& words) {
        for (int i = 0; i < words.size(); i++) {
            int m = words[i].size();
            string word = words[i];
            for (int j = 1; j <= m; ++j) {
                for (int k = 1; k <= m; ++k) {
                    string key = word.substr(0, j) + '#' + word.substr(m - k);
                    mp[key] = i;
                }
            }
        }
    }
    
    int f(string pref, string suff) {
        string target = pref + '#' + suff;
        auto it = mp.find(target);
        return it == mp.end() ? -1 : it->second;
    }
};

复杂度分析

设 $a_i$ 为第 $i$ 个单词的长度，$n$ 为输入的单词数组的长度。要查询的前缀和后缀长度分别为 $p$ 和 $s$。

时间复杂度：WordFilter() 操作为 $\sum\limits^{n-1}_{i=0}{a_i^3}$，f() 操作为 $O(p+s)$。
空间复杂度：WordFilter() 操作为 $\sum\limits^{n-1}_{i=0}{a_i^3}$，f() 操作为 $O(p+s)$。

题解2 - 字典树

设某个单词为 $egg$，将字符串 $egg#egg$ 的如下子串存入字典树：$egg#egg$、$gg#egg$、$g#egg$。
对于每次查找，将待查的字符串拼接为 $suff#pref$，即 先查询后缀再查询前缀，这样保证了匹配到后缀之后，接着匹配 $#$，然后匹配前缀。

代码

class Trie {
private:
    Trie* children[27];
    int index;
public:
    Trie() {
        memset(children, 0, sizeof(children));
    }

    void insert(const string& word, int idx) {
        Trie* node = this;
        string str = word + "#" + word;
        int n = word.size();
        int m = str.size();
        for (int i = 0; i < n; ++i) {
            Trie* curr = node;
            for (int j = i; j < m; ++j) {
                int k = str[j] == '#' ? 26 : str[j] - 'a';
                if (curr->children[k] == nullptr) {
                    curr->children[k] = new Trie();
                }
                curr = curr->children[k];
                curr->index = idx;
            }
        }
    }

    int search(const string& prefix, const string& suffix) {
        Trie* node = this;
        string str = suffix + "#" + prefix;
        for (char c: str) {
            c = c == '#' ? 26 : c - 'a';
            if (node->children[c] == nullptr) {
                return -1;
            }
            node = node->children[c];
        }
        return node->index;
    }
};
class WordFilter {
private:
    Trie* root;
public:
    WordFilter(vector<string>& words) {
        root = new Trie();
        int n = words.size();
        for (int i = 0; i < n; ++i) {
            root->insert(words[i], i);
        }
    }
    
    int f(string pref, string suff) {
        return root->search(pref, suff);
    }
};