745.前缀和后缀搜索

链接：745.前缀和后缀搜索
难度：Hard
标签：设计、字典树、数组、哈希表、字符串
简介：设计一个包含一些单词的特殊词典，并能够通过前缀和后缀来检索单词。

题解 1 - cpp

• 编辑时间：2022-07-14
• 执行用时：880ms
• 内存消耗：609.9MB
• 编程语言：cpp
• 解法介绍：头尾插入,例如插入 app,即#app, p#app, pp#app, app#app,插入所有的可能性,然后从头开始找。

#define CHILD_SIZE 27
class TrieNode {
   public:
    int key, idx;
    bool end;
    TrieNode **children;
    TrieNode(int k) {
        key = k;
        idx = -1;
        end = false;
        children = (TrieNode **)malloc(sizeof(TrieNode *) * CHILD_SIZE);
        for (int i = 0; i < CHILD_SIZE; i++) children[i] = nullptr;
    }
};
class Trie {
   public:
    TrieNode *root;
    Trie() { root = new TrieNode(0); }
    void insert(string str, int idx) {
        TrieNode *node = root;
        for (int i = 0; i < str.size(); i++) {
            int idx = str[i] == '#' ? (CHILD_SIZE - 1) : str[i] - 'a';
            if (node->children[idx] == nullptr)
                node->children[idx] = new TrieNode(idx);
            node = node->children[idx];
        }
        node->end = true;
        node->idx = idx;
    }
    TrieNode *find(string str) {
        TrieNode *node = root;
        for (int i = 0; i < str.size(); i++) {
            int idx = str[i] == '#' ? (CHILD_SIZE - 1) : str[i] - 'a';
            if (node->children[idx] == nullptr) return nullptr;
            node = node->children[idx];
        }
        return node;
    }
};
class WordFilter {
   public:
    Trie *t;
    WordFilter(vector<string> &words) {
        t = new Trie();
        for (int i = 0; i < words.size(); i++) {
            string w = words[i], insertw = "#" + w;
            for (int j = w.size() - 1; j >= 0; j--) {
                insertw = w[j] + insertw;
                t->insert(insertw, i);
            }
        }
    }
    int f(string pref, string suff) {
        TrieNode *n = t->find(suff + "#" + pref);
        int ans = -1;
        if (n == nullptr) return ans;
        dfs(ans, n);
        return ans;
    }
    void dfs(int &ans, TrieNode *n) {
        if (n->end) ans = max(ans, n->idx);
        for (int i = 0; i < CHILD_SIZE; i++) {
            if (n->children[i] == nullptr) continue;
            dfs(ans, n->children[i]);
        }
    }
};