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:

class Solution:
    def palindromePairs(self, words: List[str]) -> List[List[int]]:
        # idea: put each word reversed in a set. For each word,
        # enumerate all prefixes, if prefix in the set and the rest is palindrome, word + reverse(prefix)
        # enumerate all postfixes, if postfix in the set and rest is palindrome, reverse(postfix) + word
        all_reversed = { word[::-1]: i for i, word in enumerate(words) }
        result = set()
        for i, word in enumerate(words):
            all_reversed.pop(word[::-1])
            for j in range(len(word) + 1):
                prefix = word[:j]
                if prefix in all_reversed and self._is_palindrome(word, j, len(word) - 1):
                    result.add((i, all_reversed[prefix]))
                postfix = word[len(word)-j:len(word)]
                if postfix in all_reversed and self._is_palindrome(word, 0, len(word) - j - 1):
                    result.add((all_reversed[postfix], i))
            all_reversed[word[::-1]] = i
        return list(result)
    
    def _is_palindrome(self, word, start, end):
        while start < end:
            if word[start] != word[end]:
                return False
            start += 1
            end -= 1
        return True

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;
    }
};