题目描述

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

算法1

回文 + hashtable $O(n x L x L)$

参考文献

https://leetcode.com/problems/palindrome-pairs/solution/

C++ 代码

    // 将 每个 word reverse，加到hashtable中, reversed_w -> index;
    // 遍历每个word，将其切为 左右两部分，left | right
    // 若 right is palindrome 且 left 在 hashtable中，则 [left | right | reverse_left]是一个解, 为  {i, d[left]} 
    // 若 left is palindrome 且 right 在 hashtable中，则 [reverse_right | left | right] 是一个解，为 {d[right], i}
    // corner case: 若 候选词中有 "", 则 ""|w, w|"" 也要考虑
    // 时间复杂度: 每个词要遍历所有分割点，每个分割点要判断left 和right是否是palindrome，总体O(n x L x L)
    vector<vector<int>> palindromePairs(vector<string>& words) {
        vector<vector<int>> res;
        if(words.size()==0) return res;

        // 将 单词 逆序 加入dict
        unordered_map<string, int> d; // reversed_w -> i
        for(int i=0; i<words.size(); i++) {
            auto k = words[i];
            reverse(begin(k), end(k));
            d[k] = i;
        }

        for(int i=0; i<words.size(); i++) {
            for(int j=0; j<words[i].size(); j++) {
                auto w = words[i];
                // split to left and right
                auto left = w.substr(0, j); // can be ""
                auto right = w.substr(j);   // j<=n-1, so right wont get ""

                // 自己和自己不能组合
                if( d.count(left) && d[left]!=i && is_palin(right) ) {
                    res.push_back( {i, d[left]} );

                    // 若["" | word] 是解，则 [word|""]也是解
                    if(left.size()==0) res.push_back( {d[left], i}); 
                }

                if( d.count(right) && d[right]!=i && is_palin(left) ) {
                    res.push_back( {d[right], i} );
                }
            }
        }

        return res;
    }

    bool is_palin(string s) {
        if(s.size()<=1) return true;
        int i=0, j=s.size()-1;
        while(i<j) {
            if(s[i++] != s[j--]) return false;
        }
        return true;
    }