Palindrome Pairs -- LeetCode

[Question]

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:
Given words = ["bat", "tab", "cat"]
Return [[0, 1], [1, 0]]
The palindromes are ["battab", "tabbat"]

Example 2:
Given words = ["abcd", "dcba", "lls", "s", "sssll"]
Return [[0, 1], [1, 0], [3, 2], [2, 4]]
The palindromes are ["dcbaabcd", "abcddcba", "slls", "llssssll"]

[Analysis]
Brute force will do it in O(NxNxM), N is the number of strings in the list and M is the average length of those strings.
To lower the time complexity, use a hash table to reduce the comparison time and sort the length of strings to reduce the candidates for comparison. For each word S, compare with only words S' that are shorter. Since S' should be in the hash table, the only thing left is to make sure S- reversed(S') is a palindrome.

[Solution]
class Solution {
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
        unordered_map<string, int> pos;
        set<int> lens;
     
        for(int i=0; i<words.size(); i++) {
            pos[words[i]] = i;
            lens.insert(words[i].size());
        }
     
        auto isPal =[] (string& s, int pos, int len) {
            for (int i=pos, j=pos+len-1; i<j; i++,j-- )
                if (s[i]!=s[j]) return false;
            return true;
        };
     
        vector<vector<int>> res;
        for (int i=0; i<words.size(); i++) {
            string s = words[i];
            string rev=s;
            int s_len = s.size();
            reverse( rev.begin(), rev.end() );
         
            if (pos.count(rev) && pos[rev]!=i)
                res.push_back({i, pos[rev]});
         
            for (auto it=lens.begin(); *it<s_len; it++) {
                int len = *it;
                if (pos.count(rev.substr(0, len)) && isPal(s, 0, s_len-len ))
                    res.push_back({pos[rev.substr(0, len)], i});
             
                if (pos.count(rev.substr(s_len-len, len)) && isPal(s, len, s_len-len) )
                    res.push_back({i, pos[rev.substr(s_len-len, len)]});
            }
        }
     
        return res;
    }
};