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

解题思路
本题难度为hard, 作为算法小菜鸟，能想到的方法只有暴力循环法，两层循环把字符串拼在一起，然后判断是否为回文串，结果果然超时。好在网上有大神分享自己的解法，选了一种比较好理解的方法，在这里总结一下。

遍历数组，翻转每一个字符串，将翻转后的字符串和下标存入哈希表hash。
遍历数组，针对每个字符串在任意位置将其分为左右两个部分，ls和rs, 分别判断ls和rs是否是回文，如果ls是回文，那么判断rs是否存在于hash之中，如果存在，(假设rs翻转为sr），则sr-ls-rs构成回文串。同理，rs也回文的情况也一样。
复杂度分析：假设字符串的平均长度为k,数组长度为n, 第一层循环为n,第二次循环为k, 判断回文为k，因此复杂度为O(nkk)

具体代码如下：

class Solution {
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
        vector<vector<int> > result;
        unordered_map<string,int> dict;
        int size = words.size();
        
        string left, right,tmp;
        for(int i = 0; i < size; ++i)
        {
            tmp = words[i];
            reverse(tmp.begin(),tmp.end());
            dict[tmp] = i;
        }
        
        for(int i = 0; i < size; ++i)
        {
            for(int j = 0; j < words[i].size(); ++j)
            {
                left = words[i].substr(0,j);
                right = words[i].substr(j);
                if(dict.find(left) != dict.end() && dict[left] != i && isPalindrome(right))
                {
                    result.push_back({i, dict[left]});
                    if(left.empty())//如果为空单独判断
                        result.push_back({dict[left],i});
                }
                if(dict.find(right) != dict.end() && dict[right] != i &&
                    isPalindrome(left))
                {
                    result.push_back({dict[right], i}); 
                }
                
            }
        }
        
        return result;
    }
    
private:
    bool isPalindrome(string s)
    {
        int left = 0, right = s.size() - 1;
        while(left < right)
        {
            if(s[left] != s[right])
                return false;
            left++;
            right--;
            
        }
        return true;
    }
};

参考资料：https://discuss.leetcode.com/topic/40654/easy-to-understand-ac-c-solution-o-n-k-2-using-map/5

[leetcode] 336. Palindrome Pairs

推荐阅读更多精彩内容