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:

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"]

Solution

class Solution {
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
        unordered_map<string, int> map;
        vector<vector<int>> res;
        int n = words.size();
        for ( int i = 0; i < n; i++ ) map[words[i]] = i;
        for ( int i = 0; i < n; i++ ) {
            string s = words[i];
            int ns = s.size();
            // partition s into j and (ns-j)
            for ( int j = 0; j <= ns; j++ ) {
                string s1 = s.substr(0, j), s2 = s.substr(j);
                string rev1 = s1, rev2 = s2;
                reverse(rev1.begin(), rev1.end());
                reverse(rev2.begin(), rev2.end());
                if ( s2 == rev2 and map.find(rev1) != map.end() and map[rev1] != i) {
                    vector<int> tmp(2, i);
                    tmp[1] = map[rev1];
                    res.push_back(tmp);
                }
                if ( j != 0 and s1 == rev1 and map.find(rev2) != map.end() and map[rev2] != i) {
                    vector<int> tmp(2, i);
                    tmp[0] = map[rev2];
                    res.push_back(tmp);
                }
            }
        }
        return res;
    }
};

Notes
经典的hashTable的题目。注意一些特殊情况，比如“abcd”和“dcba”同时出现时不要重复计算一些pair。