336. Palindrome Pairs

O(n*k*k) time

class Solution {
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
        int n = words.size();
        unordered_map<string, int> m;
        for (int i = 0; i < n; ++i) {
            m[words[i]] = i;
        }
        vector<vector<int>> res;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j <= words[i].length(); ++j) { // 这里必须是<=，反例["a", ""]，否则答案会少一组，如果没有空串则不需要
                auto left = words[i].substr(0, j);
                auto right = words[i].substr(j);
                if (isValid(left)) {
                    string t(rbegin(right), rend(right));
                    if (m.count(t) && m[t] != i) {
                        res.push_back({m[t], i});
                    }
                }
                if (!right.empty() && isValid(right)) { // 这里要对right判空，因为之前left已经处理过完整字符串了，避免重复处理添加，反例["ab", "ba"]
                    string t(rbegin(left), rend(left));
                    if (m.count(t) && m[t] != i) {
                        res.push_back({i, m[t]});
                    }
                }
            }
        }
        return res;
    }

    bool isValid(const string &s) {
        int l = 0, r = s.length() - 1;
        while (l < r) {
            if (s[l++] != s[r--]) return false;
        }
        return true;
    }
};

Trie版本O(n*k²)k是每个单词平均长度，n是单词个数

class Solution {
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
        Trie t;
        int n = words.size();
        for (int i = 0; i < n; ++i) {
            t.add(words, i);
        }
        vector<vector<int>> res;
        for (int i = 0; i < n; ++i) {
            for (auto idx : t.find(words[i])) {
                if (idx != i && isPalindrome(words[i] + words[idx])) { // 连接所有的可能单词并检查合法性
                    res.push_back({i, idx});
                }
            }
        }
        return res;
    }

    bool isPalindrome(const string &s) {
        int n = s.length();
        int i = 0, j = n - 1;
        for (; i < j && s[i] == s[j]; ++i, --j);
        return i >= j;
    }

    struct TrieNode {
        TrieNode() : idx(-1), children({nullptr}) {}
        TrieNode *children[26];
        int idx; // 如果单词到此结束，保存其下标
        vector<int> indices; // 保存所有长度大于等于 到此为止的单词 的单词的下标
    };

    struct Trie {
        Trie() : root(new TrieNode()) {}
        void add(const vector<string> &words, int idx) {
            auto node = root;
            for (auto rit = words[idx].rbegin(); rit != words[idx].rend(); ++rit) {
                if (!node->children[*rit - 'a']) {
                    node->children[*rit - 'a'] = new TrieNode();
                }
                node->indices.push_back(idx); // 如果当前单词不在此结束，当前节点保存该单词的下标
                node = node->children[*rit - 'a'];
            }
            node->idx = idx; // 当前单词结束于此，保存其下标
            node->indices.push_back(idx);
        }
        vector<int> find(const string &s) {
            auto node = root;
            vector<int> res;
            for (const auto &c : s) {
                if (!node->children[c - 'a']) {
                    res.insert(res.end(), node->indices.begin(), node->indices.end()); // 虽然当前查找的目标单词不在Trie上，但是仍然要把一路遇到的所有下标以及本来继续往下可能会遇到的所有下标全部返回
                    return res;
                } else {
                    if (node->idx != -1) {
                        res.push_back(node->idx); // 路过此节点，保存其代表的单词的下标
                    }
                    node = node->children[c - 'a'];
                }
            }
            res.insert(res.end(), node->indices.begin(), node->indices.end());
            return res;
        }
        TrieNode *root;
    };
};