336. 回文对

class Solution {
public:
    bool isPalindrome(string word, int left, int right) {
        while (left < right)
            if(word[left++] != word[right--]) return false;
        return true;
    }
   
    string reverse(string tmp)
    {
        string ret;
        for (int i = tmp.length() - 1; i >= 0; i--)
        {
            ret.push_back(tmp[i]);
        }
        return ret;
    }
   
    vector<vector<int>> palindromePairs(vector<string>& words) {
       
        vector<vector<int>> ret;
       
        map<string, int> index;
        set<int> st;
       
        for (int i = 0; i < words.size(); i++)
        {
            index[words[i]] = i;
            st.insert(words[i].size());
        }
       
        for (int i = 0; i < words.size(); i++)
        {
            string tmp = words[i];
            tmp = reverse(tmp);
            if (index.find(tmp) != index.end() && index[tmp] != i)
            {
                vector<int> ret1;
                ret1.push_back(i);
                ret1.push_back(index[tmp]);
                ret.push_back(ret1);
            }
           
            for (set<int>::iterator it = st.begin(); it != st.find(tmp.length()); it++)
            {
                string left = tmp.substr(0, *it);
                string right = tmp.substr(tmp.length() - *it);

                if (index.find(left) != index.end() && isPalindrome(tmp, *it, tmp.length() - 1))
                {
                    vector<int> ret1;
                    ret1.push_back(index[left]);
                    ret1.push_back(i);
                    ret.push_back(ret1);
                }

                if (index.find(right) != index.end() && isPalindrome(tmp, 0, tmp.length() - *it - 1))
                {
                    vector<int> ret1;
                    ret1.push_back(i);
                    ret1.push_back(index[right]);
                    ret.push_back(ret1);
                }
            }
       
        }
       
        return ret;
    }
};