题目描述

给定一个单词数组，不包含相同单词。请找出所有的下标对(i, j)，满足words[i] + words[j] 是回文串。

样例1

给定 words = ["bat", "tab", "cat"]
返回 [[0, 1], [1, 0]]
解释：这两个回文串分别是 ["battab", "tabbat"]

样例2

给定 words = ["abcd", "dcba", "lls", "s", "sssll"]
返回 [[0, 1], [1, 0], [3, 2], [2, 4]]
解释：这4个回文串分别是 ["dcbaabcd", "abcddcba", "slls", "llssssll"]

算法

(回文串，哈希表) $O(nL^2)$

首先，我们先来分析一下两个单词组成的回文串有什么性质。如下图所示：

ac和cd分别表示两个单词，不妨假设cd较短。我们在线段中找到b点，使得 $l_{ab} = l_{cd}$。
则ad为回文串，等价于ab和cd的逆序相等，且bc是回文串。

所以我们可以将所有单词的逆序存入哈希表，然后先枚举每个单词，再枚举每个单词的b点的位置，然后在哈希表中查找是否存在一个单词和ab相等，且bc是回文串，如果是 true，则找到了一组解。

时间复杂度分析：令 $n$ 表示单词个数，$L$ 表示单词的平均长度。枚举单词的计算量是 $O(n)$，对每个单词枚举b点的位置的计算量是 $O(L)$，判断回文串的计算量是 $O(L)$，所以总时间复杂度是 $O(nL^2)$。

C++ 代码

class Solution {
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
        unordered_map<string, int> S;
        for (int i = 0; i < words.size(); i ++ )
        {
            string key = words[i];
            reverse(key.begin(), key.end());
            S[key] = i;
        }
        vector<vector<int>> res;
        if (S.count(""))
        {
            for (int i = 0; i < words.size(); i ++ )
                if (words[i] != "" && is_palindrome(words[i]))
                    res.push_back({S[""], i});
        }
        for (int i = 0; i < words.size(); i ++ )
            for (int j = 0; j < words[i].size(); j ++ )
            {
                string left = words[i].substr(0, j);
                string right = words[i].substr(j);
                if (S.count(left) && is_palindrome(right) && S[left] != i) res.push_back({i, S[left]});
                if (S.count(right) && is_palindrome(left) && S[right] != i) res.push_back({S[right], i});
            }
        return res;
    }

    bool is_palindrome(string &word)
    {
        for (int i = 0, j = word.size() - 1; i < j; i ++ , j -- )
            if (word[i] != word[j])
                return false;
        return true;
    }
};