<p>You are given a <strong>0-indexed</strong> array of <strong>unique</strong> strings <code>words</code>.</p>

<p>A <strong>palindrome pair</strong> is a pair of integers <code>(i, j)</code> such that:</p>

<ul>
	<li><code>0 &lt;= i, j &lt; words.length</code>,</li>
	<li><code>i != j</code>, and</li>
	<li><code>words[i] + words[j]</code> (the concatenation of the two strings) is a <span data-keyword="palindrome-string">palindrome</span>.</li>
</ul>

<p>Return <em>an array of all the <strong>palindrome pairs</strong> of </em><code>words</code>.</p>

<p>You must write an algorithm with&nbsp;<code>O(sum of words[i].length)</code>&nbsp;runtime complexity.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> words = [&quot;abcd&quot;,&quot;dcba&quot;,&quot;lls&quot;,&quot;s&quot;,&quot;sssll&quot;]
<strong>Output:</strong> [[0,1],[1,0],[3,2],[2,4]]
<strong>Explanation:</strong> The palindromes are [&quot;abcddcba&quot;,&quot;dcbaabcd&quot;,&quot;slls&quot;,&quot;llssssll&quot;]
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> words = [&quot;bat&quot;,&quot;tab&quot;,&quot;cat&quot;]
<strong>Output:</strong> [[0,1],[1,0]]
<strong>Explanation:</strong> The palindromes are [&quot;battab&quot;,&quot;tabbat&quot;]
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> words = [&quot;a&quot;,&quot;&quot;]
<strong>Output:</strong> [[0,1],[1,0]]
<strong>Explanation:</strong> The palindromes are [&quot;a&quot;,&quot;a&quot;]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= words.length &lt;= 5000</code></li>
	<li><code>0 &lt;= words[i].length &lt;= 300</code></li>
	<li><code>words[i]</code> consists of lowercase English letters.</li>
</ul>

class Solution {
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
        unordered_map<string_view,int> wordsSet;
        unordered_set<uint64_t> setOut;
        vector<vector<int>> out;
        //split the words by depth, ie: abcd a, ab, abc, abcd
        for (int i = 0; i < words.size(); i++) {
            if (words[i].size())
                wordsSet[words[i]] = i;
        }


        int emptyIdx = -1;
        for (int i = 0; i< words.size();i++) {
            auto word = words[i];
            if (word.size()) {

                for (int n = 0; n < word.size() + 1; n++) {

                    bool palindrome = true;
                    //if (n) {
                    //    auto front = word.substr(0, n);
                    //    auto reversedfront = front;
                    //    reverse(reversedfront.begin(), reversedfront.end());
                    //    palindrome = (front == reversedfront);
                    //}
                    for (size_t s = 0; s < n/2; s++) {
                        if (word[s] != word[n - 1 - s]) {
                            palindrome = false;
                            break;
                        }
                    }
                    if (palindrome) {
                        string reverseword = word.substr(n, word.size());
                        reverse(reverseword.begin(), reverseword.end());
                        auto it = wordsSet.find(reverseword);
                        if ((wordsSet.find(reverseword) != wordsSet.end()) && (it->second != i)) {
                            

                            
                            setOut.insert((uint64_t(it->second) << 32) | i);
                            //cout << "[1] " << it->second << " " << i << "\n";
                            //out.emplace_back(vector<int>{it->second,i});

                        }
                    }

                }


                for (int n = 1; n < word.size(); n++) {
                    bool palindrome = true;

                    for (size_t s = 0; s < (word.size()-n) / 2; s++) {
                        if (word[s+n] != word[word.size() - 1 - s]) {
                            palindrome = false;
                            break;
                        }
                    }
                    //auto back = word.substr(n, word.size());
                    //auto reversedback = back;
                    //reverse(reversedback.begin(), reversedback.end());
                    //palindrome = (back == reversedback);
       

                    //for (size_t s = n+1; s < n; s++) {
                    //    if (word[s] != word[n - 1 - s]) {
                    //        palindrome = false;
                    //        break;
                    //    }
                    //}
                    if (palindrome) {
                        string reverseword = word.substr(0, n);
                        reverse(reverseword.begin(), reverseword.end());
                        auto it = wordsSet.find(reverseword);
                        if ((wordsSet.find(reverseword) != wordsSet.end()) && (it->second != i)) {

                            setOut.insert((uint64_t(i) << 32) | it->second);
                            //cout << "[2] " << i << " " << it->second << "\n";
                            //out.emplace_back(vector<int>{i, it->second});
                        }
                    }

                }

            }
            else
                emptyIdx = i;
        }
        out.reserve(setOut.size());
        for (const auto packed : setOut) {
            out.emplace_back(vector<int>{int(packed >> 32), int((packed << 32) >> 32)});
            
        }

        if (emptyIdx != -1) {

            for (int i = 0; i < words.size(); i++) {
                if (i != emptyIdx) {
                    auto reverseword = words[i];
                    reverse(reverseword.begin(), reverseword.end());
                    if (reverseword == words[i]) {
                        out.insert(out.end(), { {emptyIdx,i},{i,emptyIdx} });
                    }
                }
            }

        }
        return out;
    }
};
452981