336. Palindrome Pairs

• Difficulty: Hard

• Topics: Hash Table, String, Trie

• Similar Questions:

  • Longest Palindromic Substring

  • Shortest Palindrome

Problem:

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

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

Solutions:

class Solution {
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
        vector<vector<int>> left = helper(words, true);
        vector<string> reverseWords;
        for (int i = 0; i < words.size(); ++i) {
            reverseWords.push_back({words[i].rbegin(), words[i].rend()});
        }
        vector<vector<int>> right = helper(reverseWords,false);
        set<vector<int>> ret;
        ret.insert(right.begin(), right.end());
        ret.insert(left.begin(), left.end());
        return vector<vector<int>>(ret.begin(), ret.end());
    }


    vector<vector<int>> helper(vector<string>& words, bool direction) {
        unordered_map<string, int> wordMap;
        for (int i = 0; i < words.size(); ++i) {
            wordMap[words[i]] = i;
        }

        vector<vector<int>> ret;
        for (int i = 0; i < words.size(); ++i) {
            string word = words[i];
            reverse(word.begin(), word.end());
            for (int j = word.length() - 1; j >= -1; --j) {   
                if (wordMap.count(word.substr(0, j + 1)) > 0 && isPalindrome(word.substr(j + 1, word.length() - j - 1))) {
                    if (i != wordMap[word.substr(0, j + 1)]) {
                        if (direction) // Two directions!!!
                            ret.push_back({wordMap[word.substr(0, j + 1)], i});
                        else 
                            ret.push_back({i, wordMap[word.substr(0, j + 1)]});
                        continue;
                    }
                }
            }
        }

        return ret;
    }

private:
    bool isPalindrome(string str) {
        //cout << str << endl;
        int left = 0;
        int right = str.length() - 1;
        while (left < right) {
            if (str[left] != str[right])    return false;
            ++left;
            --right;
        }
        return true;
    }

};