336. Palindrome Pairs

Given a list of unique words, find all pairs of distinct indices (i, j) in the given list, so that the concatenation of the two words, i.e. words[i] + words[j] is a palindrome.

Example 1:

Input: ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]] 
Explanation: The palindromes are ["dcbaabcd","abcddcba","slls","llssssll"]

Example 2:

Input: ["bat","tab","cat"]
Output: [[0,1],[1,0]] 
Explanation: The palindromes are ["battab","tabbat"]

// Hashmap + Treeset
bool isValid(const string& s, int i, int j) {
    while (i < j) {
        if (s[i++] != s[j--]) return false;
    }
    return true;
}
vector<vector<int>> palindromePairs(vector<string>& words) {
    vector<vector<int> > res;
    unordered_map<string, size_t> str2idx;
    set<size_t> strLen;
    for (size_t i = 0; i < words.size(); ++i) {
        str2idx[words[i]] = i;
        strLen.insert(words[i].length());
    }
    for (size_t i = 0; i < words.size(); ++i) {
        string tmp = words[i];
        size_t len = tmp.length();
        reverse(tmp.begin(), tmp.end());
        if (str2idx.count(tmp) && str2idx[tmp] != i) { // avoid some palindromic words
            res.push_back({i, str2idx[tmp]});
        }
        const auto len_it = strLen.find(len);
        if (len_it == strLen.end()) continue;
        for (auto it = strLen.begin(); it != len_it; ++it) {
            int d = *it;
            // Two cases
            // (1) cur + tmp[d...len - 1]
            if (isValid(tmp, 0, len - 1 - d) && str2idx.count(tmp.substr(len - d))) {
                res.push_back({i, str2idx[tmp.substr(len - d)]});
            }
            // (1) tmp[0...d - 1] + cur
            if (isValid(tmp, d, len - 1) && str2idx.count(tmp.substr(0, d))) {
                res.push_back({str2idx[tmp.substr(0, d)], i});
            }
        }
    }
    return res;
}

// Hashmap
bool isValid(const string& s) {
    for (size_t i = 0; i < s.size() / 2; ++i) {
        if (s[i] != s[s.size() - 1 - i]) return false;
    }
    return true;
}
vector<vector<int>> palindromePairs(vector<string>& words) {
    vector<vector<int> > res;
    unordered_map<string, int> str2idx;
    for (int i = 0; i < words.size(); ++i) {
        str2idx[words[i]] = i;
    }
    for (int i = 0; i < words.size(); ++i) {
        int l = 0, r = 0;
        while (l <= r) {
            string tmp = words[i].substr(l, r - l);
            reverse(tmp.begin(), tmp.end());
            if (str2idx.count(tmp) && 
                str2idx[tmp] != i && 
                isValid(words[i].substr((l == 0 ? r : 0), (l == 0 ? words[i].size() - r: l) ) ) ) {
                if (l == 0) res.push_back({i, str2idx[tmp]});
                else res.push_back({str2idx[tmp], i});
            }
            if (r < words[i].length()) ++r;
            else ++l;
        }
    }
    return res;
}

// Trie
class TrieNode {
public:
    int idx;
    vector<TrieNode*> next;
    vector<int> list;
    TrieNode() : idx(-1), next(26, nullptr) {}
    ~TrieNode() {
        for (TrieNode* n : next) {
            delete n;
        }
        list.clear();
    }
};
bool isValid(const string& s, int i, int j) {
    while (i < j) {
        if (s[i++] != s[j--]) return false;
    }
    return true;
}
void addWord(TrieNode* root, const string& word, int index) {
    for (int i = word.length() - 1; i >= 0; --i) {
        int j = word[i] - 'a';
        if (!root->next[j]) root->next[j] = new TrieNode();
        if (isValid(word, 0, i)) root->list.emplace_back(index);
        root = root->next[j];
    }
    root->list.emplace_back(index);
    root->idx = index;
}
void search(const vector<string>& words, int i, TrieNode* root, vector<vector<int> >& res) {
    for (int j = 0; j < words[i].length(); ++j) {
        if (root->idx >= 0 && root->idx != i && isValid(words[i], j, words[i].length() - 1)) {
            res.push_back({i, root->idx});
        }
        if (!root->next[words[i][j] - 'a']) return;
        root = root->next[words[i][j] - 'a'];
    }
    for (int j : root->list) {
        if (i == j) continue;
        res.push_back({i, j});
    }
}
vector<vector<int>> palindromePairs(vector<string>& words) {
    vector<vector<int> > res;
    TrieNode* root = new TrieNode();
    int n = words.size();
    for (int i = 0; i < n; ++i) addWord(root, words[i], i);
    for (int i = 0; i < n; ++i) search(words, i, root, res);
    delete root;
    return res;
}