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

## Thoughts

在一堆字符串中找出能拼成回文的pair。一个str可以看成l和r两部分，然后可能有两种和其它str拼成回文的方法：rev\_r l r和l r rev\_l。因此把组内所有reverserd存进hash map中，然后对每一个词遍历所有的划分，看l自身是回文的情况下，map中有没有rev\_r；r同理。因为空串的存在，所有的划分包含了null(l) s(r)和s(l) null。 为了避免rev\_r null r和l null rev\_l 给出重复结果，第二个判断条件加检查l是否为空。

## Code

```
/*
 * @lc app=leetcode id=336 lang=cpp
 *
 * [336] Palindrome Pairs
 */

// @lc code=start
class Solution {
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
        const int N = words.size();
        unordered_map<string, int> dict;
        for (int i = 0; i < N; ++i) {
            auto rw = words[i];
            reverse(rw.begin(), rw.end());
            dict[rw] = i;
        }
        const auto palind = [](const string &s) {
            for (int i = 0, j = s.length() - 1; i < j; ++i, --j) {
                if (s[i] != s[j]) return false;
            }
            return true;
        };
        vector<vector<int>> res;
        for (int i = 0; i < N; ++i) {
            const auto w = words[i];
            for (int j = 0; j <= w.length(); ++j) {
                const auto l = w.substr(0, j), r = w.substr(j);
                if (dict.count(l) && dict[l] != i && palind(r)) {
                    res.push_back({i, dict[l]});
                }
                if (dict.count(r) && dict[r] != i && palind(l) && !l.empty()) {
                    res.push_back({dict[r], i});
                }
            }
        }
        return res;
    }
};
// @lc code=end


```

## Analysis

时间复杂度O(N).