class Solution {
public:
    bool isPalindrome(string s) {
        if (s.size() <= 1) return true;
        int i = 0;
        int j = s.size() - 1;
        while (i < j) {
            if (s[i++] != s[j--]) return false;
        }

        return true;
    }

    vector<vector<int>> palindromePairs(vector<string>& words) {
        vector<vector<int>> res;
        if (!words.size()) return res;
        unordered_map<string, int> word_idx;
        for (int i = 0; i < words.size(); ++i) {
            word_idx[words[i]] = i;
        }
        vector<int> slu(2);
        for (int i = 0; i < words.size(); ++i) {
            int len = words[i].length();
            for (int l = 0; l <= len; ++l) {
                string left = words[i].substr(0, l);
                string right = words[i].substr(l);
                string rleft = left;
                string rright = right;
                reverse(rleft.begin(), rleft.end());
                reverse(rright.begin(), rright.end());
                if (word_idx.find(rleft) != word_idx.end()) {
                    if (word_idx[rleft] != i && isPalindrome(right)) {
                        res.push_back({i,word_idx[rleft]});
                    }

                }
                if (l != 0 && word_idx.find(rright) != word_idx.end()) {
                    if (word_idx[rright] != i && isPalindrome(left)) {
                        res.push_back({word_idx[rright],i});
                    }

                }

            }
        }
        return res;
    }
};