745. Prefix and Suffix Search

trie的应用 构造函数 O(nm) n是单词个数 m是单词长度 查询函数 O(k) k是prefix+suffix长度 空间复杂度 O(nm^2) 因为每个单词都可以派生出m个单词 每个单词长度为m 共n个单词 就是nmm
这道题最tricky的地方是如何存单词
Consider the word ‘apple’. For each suffix of the word, we could insert that suffix, followed by ‘#’, followed by the word, all into the trie.

For example, we will insert ‘#apple’, ‘e#apple’, ‘le#apple’, ‘ple#apple’, ‘pple#apple’, ‘apple#apple’ into the trie. Then for a query like prefix = “ap”, suffix = “le”, we can find it by querying our trie for le#ap.

class WordFilter {
public:

    struct TrieNode {
        TrieNode *children[27] = {nullptr};
        bool isEnd = false;
        int weight = 0;
    };

    WordFilter(vector<string> words) {
        int n = words.size();
        for (int i = 0; i < n; ++i) {
            auto t = words[i];
            int m = t.length();
            for (int j = m; j >= 0; --j) {
                add(root, t.substr(j) + "{" + words[i], i);
            }
        }
    }

    int f(string prefix, string suffix) {
        return search(root, suffix + "{" + prefix);
    }

    void add(TrieNode *root, const string &s, int weight) {
        auto p = root;
        for (char c : s) {
            if (!p->children[c - 'a']) {
                p->children[c - 'a'] = new TrieNode;
            }
            p->weight = weight; // 因为是从前往后insert单词所以权重可以直接覆盖
            p = p->children[c - 'a'];
        }
        p->isEnd = true;
        p->weight = weight;
    }

    int search(TrieNode *root, const string &s) {
        auto p = root;
        for (char c : s) {
            if (!p->children[c - 'a']) return -1;
            p = p->children[c - 'a'];
        }
        return p->weight;
    }

    TrieNode *root = new TrieNode;
};

/**
 * Your WordFilter object will be instantiated and called as such:
 * WordFilter obj = new WordFilter(words);
 * int param_1 = obj.f(prefix,suffix);
 */

TLE

class WordFilter {
public:

    struct TrieNode {
        TrieNode *children[26] = {nullptr};
        bool isEnd = false;
        vector<pair<string, int>> words;
        int weight = 0;
    };

    WordFilter(vector<string> words) {
        int n = words.size();
        for (int i = 0; i < n; ++i) {
            add(root, words[i], i);
        }
    }

    int f(string prefix, string suffix) {
        int res = -1;
        for (auto &&p : getWords(root, prefix)) {
            if (endsWith(p.first, suffix)) {
                res = max(res, p.second);
            }
        }
        return res;
    }

    void add(TrieNode *root, const string &s, int weight) {
        auto p = root;
        for (char c : s) {
            int key = c - 'a';
            if (!p->children[key]) {
                p->children[key] = new TrieNode;
            }
            p->words.emplace_back(s, weight);
            p = p->children[key];
        }
        p->words.emplace_back(s, weight);
        p->isEnd = true;
        p->weight = weight;
    }

    vector<pair<string, int>> getWords(TrieNode *root, const string &prefix) {
        auto p = root;
        for (char c : prefix) {
            int key = c - 'a';
            if (!p->children[key]) return {};
            p = p->children[key];
        }
        return p->words;
    }

    bool endsWith(const string &s, const string &suffix) {
        if (suffix.empty()) return true;
        int m = s.length(), n = suffix.length();
        for (int i = m - 1, j = n - 1; i >= 0 && j >= 0; --i, --j) {
            if (s[i] != suffix[j]) return false;
        }
        return true;
    }

    TrieNode *root = new TrieNode;

};

/**
 * Your WordFilter object will be instantiated and called as such:
 * WordFilter obj = new WordFilter(words);
 * int param_1 = obj.f(prefix,suffix);
 */