palindrome-pairs

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

Algorithms

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

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

<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 palindrome.</li>
</ul>

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

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

&nbsp;
Example 1:

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

Example 2:

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

Example 3:

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

&nbsp;
Constraints:

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