336. Palindrome Pairs

class Solution {
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
        vector<vector<int>> res;
        unordered_map<string, int> reversed;
        for (int i = 0; i < words.size(); i++) {
            string tmp = words[i];
            reverse(tmp.begin(), tmp.end());
            reversed[tmp] = i;
        }

        for (int i = 0; i < words.size(); i++) {//cout<<endl<<words[i]<<endl;
            for (int k = 0; k < words[i].size(); k++){
                string l = words[i].substr(0, k);
                string r = words[i].substr(k, words[i].size() - k);
                if (reversed.count(l) && reversed[l] != i && isPalindorme(r)) {
                    res.push_back({i, reversed[l]});
                    if (l == "") res.push_back({reversed[l], i});
                }
                if (reversed.count(r) && reversed[r] != i && isPalindorme(l)) 
                    res.push_back({reversed[r], i});
            }
        }

        return res;
    }
private:
    bool isPalindorme(string s) {
        for (int i = 0; i < s.size()/2; i++)
            if (s[i] != s[s.size() - 1 - i]) return false;
        return true;
    }
};

unfinished trie, you can check this java

class TrieNode {
public:
    int idx;    //need a list to store those words that begin to being palindrome from this node to the end
    vector<TrieNode*> children;
    TrieNode() {
        idx = -1;
        children = vector<TrieNode*>(26, NULL);
    }
};

class Trie {
public:
    TrieNode* getRoot() {return root;}
    Trie(vector<string>& words) {
        root = new TrieNode();
        for (int i = 0; i < words.size(); i++)
            addWord(w, i);
    }
private:
    TrieNode* root;
    void addWord(string w, int idx) {
        TrieNode*curr = root;
        for (char c : w) {
            if (curr->children[c - 'a'] == NULL)
                curr->children[c - 'a'] = new TrieNode();
            curr = curr->children[c - 'a'];
        }
        curr->idx = idx;
    }
};

class Solution {
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
        Trie trie = new Trie(words);
        root = trie->getRoot;
        for (int i = 0; i < words.size(); i++)
            digTrie(words[i], i);
        return res;
    }
private:
    TrieNode *root;
    vector<vector<int>> res;
    void digTrie(string word, int ID) {
        TrieNode *curr = root;
        int i;
        for (i = word.size() - 1; i >= 0; i--)
            if (curr->children[word[i] - 'a']) curr = curr->children[word[i] - 'a'];
                else break;
        if (curr->idx != -1 && i == -1) res.emplace(curr->idx, ID);
        if (i == -1) isPalinNode(curr, "", ID);
            else if (curr->idx != -1 && isPalinS(word.substr(0, i + 1)))
                res.emplace(curr->idx, ID);
        return;
    }
    void isPalinNode(TreeNode *curr, string s, int ID) {
        for (int i = 0; i < 26; i++)
            if (root->children[i]) {
                s += i + 'a'
            }
    }
};