<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 {
void fillPalindrome(vector<string> &words)
{
    for(auto word : words)
    {
        string rev = word;
        reverse(rev.begin(),rev.end());
        if(rev==word)
            palin[word]=1;
        else
            palin[word]=0;
    }
}
bool isPalindrome(string &s)
{
    if(palin.find(s)!=palin.end())
        return palin[s];
  int i = 0 ;
  int j =s.length()-1;
  while(i<j)
  {
    if(s[i]!=s[j])
        return false;
    i++;
    j--;
  }
  return true;

}
unordered_map<string,bool> palin;
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
        fillPalindrome(words);
        unordered_map<string, int > data;
        int i = 0 ;
        //fill data with map
        for(auto word: words)
        {
            data[word]=i;
            i++;
        } 

        int index = 0 ;
        vector<vector<int>> ans;
        for(auto word : words)
        {
            string remWord = "";
            string currWord = "";
            // check for substring
            if(word=="")
            {
                for(int i =0 ; i<words.size();i++)
                {
                    if(i==index)
                        continue;
                    if(isPalindrome(words[i]))
                        ans.push_back({i,index});
                }
                index++;
                continue;
            }
            currWord = word;
            for(int i = 0 ; i<word.length(); i++)
            {
  
                if(isPalindrome(currWord) )
                {
                    if(data.find(remWord)!=data.end() && data[remWord]!=index)
                    {
                        ans.push_back({data[remWord],index});
                    }
                }
                if(isPalindrome(remWord))
                {
                    string currWord_rev = currWord;
                    reverse(currWord_rev.begin(),currWord_rev.end());
                    if(data.find(currWord_rev)!=data.end() && data[currWord_rev]!=index)
                    {
                        ans.push_back({index,data[currWord_rev]});
                    }
                }
                currWord.pop_back();
                remWord += word[word.length()-1-i];
            }
            index++;
        }
        return ans; 
    }
};
402559