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:

Input: ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]] 
Explanation: The palindromes are ["dcbaabcd","abcddcba","slls","llssssll"]

Example 2:

Input: ["bat","tab","cat"]
Output: [[0,1],[1,0]] 
Explanation: The palindromes are ["battab","tabbat"]

Solution

Approach 1: O(NxNxL): N is the size of words; L is the average length of each word. (Time Limit Exceeded.)

Approach 2: O(NxLxL): N is the size of words; L is the average length of each word. If the length of each word is not too long.

Code (Python)

Approach 1:

Approach 2:

Code (C++)

Approach 1:

// Time Limit Exceeded.
class Solution {
private:
    bool isPal(string s) {
        int head = 0;
        int tail = s.size() - 1;
        while (head < tail)
        {
            if (s[head] != s[tail])
                return false;
            head++;
            tail--;
        }
        return true;
    }
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
        vector<vector<int>> res;
        int n = words.size();
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (i == j)
                    continue;
                if (isPal(words[i] + words[j]))
                {
                    vector<int> tmp;
                    tmp.push_back(i);
                    tmp.push_back(j);
                    res.push_back(tmp);
                }
            }
        }
        return res;
    }
};

Approach 2:

// If the length of each word is not too long.
// * ["a",""] should be [[0,1],[1,0]].
//   ["abcd","dcba"] shouldn't be [[0,1],[1,0],[0,1],[1,0]].
class Solution {
private:
    bool isPal(string s) {
        int head = 0;
        int tail = s.size() - 1;
        while (head < tail)
        {
            if (s[head] != s[tail])
                return false;
            head++;
            tail--;
        }
        return true;
    }
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
        unordered_map<string,int> umap;
        for (int i = 0; i < words.size(); ++i)
        {
            umap[words[i]] = i;
        }
        vector<vector<int>> res;
        for (int i = 0; i < words.size(); ++i)
        {
            for (int j = 0; j <= words[i].size(); ++j)
            {
                // For each word, try getting the palindrome from its prefix.
                if (j > 0 && isPal(words[i].substr(0, j))) // "j > 0" (see * above).
                {
                    string rightRev = words[i].substr(j);
                    std::reverse(rightRev.begin(), rightRev.end());
                    if (umap.find(rightRev) != umap.end() && umap[rightRev] != i)
                    {
                        vector<int> tmp;
                        tmp.push_back(umap[rightRev]);
                        tmp.push_back(i);
                        res.push_back(tmp);
                    }
                }
                // Then try getting the palindrome from its suffix.
                if (isPal(words[i].substr(j)))
                {
                    string leftRev = words[i].substr(0, j);
                    std::reverse(leftRev.begin(), leftRev.end());
                    if (umap.find(leftRev) != umap.end() && umap[leftRev] != i)
                    {
                        vector<int> tmp;
                        tmp.push_back(i);
                        tmp.push_back(umap[leftRev]);
                        res.push_back(tmp);
                    }
                }
            }
        }
        return res;
    }
};