[leetcode] 336. Palindrome Pairs

Description

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

分析

• 要用到哈希表來建立每個單詞和其位置的映射，然後需要一個set來儲存出現過的單詞的長度，算法的思想是，周遊單詞集，對于周遊到的單詞，對其翻轉一下，然後在哈希表查找翻轉後的字元串是否存在，注意不能和原字元串的坐标位置相同，因為有可能一個單詞翻轉後和原單詞相等。
• 現在隻是處理了bat和tab的情況，還存在abcd和cba，dcb和abcd這些情況需要考慮，這就需要用set，由于set是自動排序的，可以找到目前單詞長度在set中的iterator，然後從開頭開始周遊set，周遊比目前單詞小的長度，比如abcdd翻轉後為ddcba，發現set中有長度為3的單詞，然後判斷dd是否為回文串，若是，再看cba是否存在于哈希表，若存在，則說明abcdd和cba是回文對，存入結果中；
• 對于dcb和aabcd這類的情況也是同樣處理，我們要在set裡找的字元串要在周遊到的字元串的左邊和右邊分别嘗試，看是否是回文對，這樣周遊完單詞集，就能得到所有的回文對。

代碼

class Solution {
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
        vector<vector<int>> res;
        unordered_map<string,int> m;
        set<int> s;
        for(int i=0;i<words.size();i++){
            m[words[i]]=i;
            s.insert(words[i].size());
        }
        for(int i=0;i<words.size();i++){
            string t=words[i];
            int len=words[i].size();
            reverse(t.begin(),t.end());
            if(m.count(t)&&m[t]!=i){
                res.push_back({i,m[t]});
            }
            auto a=s.find(len);
            for(auto it=s.begin();it!=a;it++){
                int d=*it;
                if(isValid(t,0,len-d-1)&&m.count(t.substr(len-d))){
                    res.push_back({i,m[t.substr(len-d)]});
                }
                if(isValid(t,d,len-1)&&m.count(t.substr(0,d))){
                    res.push_back({m[t.substr(0,d)],i});
                }
            }
        }
        return res;
    }
    bool isValid(string t,int left,int right){
        while(left<right){
            if(t[left++]!=t[right--]) return false;
        }
        return true;
    }
};      

參考文獻