# LeetCode-Palindrome Pairs Solution

#### 问题

Given a list of unique words, return all the pairs of the distinct indices `(i, j)` in the given list, so that the concatenation of the two words `words[i] + words[j]` is a palindrome.

Example 1:

Input:

``` words = ["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:

``` words = ["bat","tab","cat"]
```

Output:

``` [[0,1],[1,0]]
```

Explanation:

``` The palindromes are ["battab","tabbat"]
```

Example 3:

Input:

``` words = ["a",""]
```

Output:

``` [[0,1],[1,0]]
```

Constraints:

• `1 <= words.length <= 5000`
• `0 <= words[i].length <= 300`
• `words[i]` consists of lower-case English letters.

#### 解答

##### Trie：

1. 构造：Trie树的构造单词反序存放，并增加一个单词结束标识。
2. 匹配：
• 当要查找单词A比当前Trie分支上的单词B长：前面匹配均成功，需要判断要找到单词A多出部分是不是回文。
• 当要查找单词A比当前Trie分支上的单词B短：前面匹配均成功，需要判断该分支上的单词剩余部分是不是回文。

[“acbe”, “ca”, “bca”, “bbac”].

from https://fizzbuzzed.com/top-interview-questions-5/

```class Solution:
def getPalindromesForWord(self, trie, word, index):
output = []
while word:
if trie.wordEndIndex >= 0:
if isPalindrome(word):
output.append(trie.wordEndIndex)
if not word[0] in trie.paths:
return output
trie = trie.paths[word[0]]
word = word[1:]
if trie.wordEndIndex >=0:
output.append(trie.wordEndIndex)
output.extend(trie.palindromesBelow)
return output

def palindromePairs(self, words: List[str]) -> List[List[int]]:
trie = makeTrie(words)
output=[]
for i, word in enumerate(words):
candidates = self.getPalindromesForWord(trie, word, i)
output.extend([[i,c] for c in candidates if i!= c])
return output

def isPalindrome(word):
if len(word) == 0 or len (word) == 1:
return True
return word[0] == word[-1] and isPalindrome(word[1:-1])

class Trie:
def __init__(self):
self.paths = defaultdict(Trie)
self.wordEndIndex = -1
self.palindromesBelow = []
trie = self
for j , char in enumerate(reversed(word)):
if isPalindrome(word[0:len(word)-j]):
trie.palindromesBelow.append(index)
trie = trie.paths[char]
trie.wordEndIndex = index

def makeTrie(words):
trie = Trie()
for i, word in enumerate(words):
return trie```
##### 穷举：

```def isPalindrome(word):
for i in range(len(word)//2):
if word[i] != word[-1-i]:
return False
return True

def isPalindrome2(word):
if len(word) == 0 or len(word) == 1:
return True
return word[0] == word[-1] and isPalindrome2(word[1:-1])

def isPalindrome3(word):
return word == word[::-1]

def palidromePairs(words):
output = []
for i, firstword in enumerate(words):
for j, secondword in enumerate(words):
if (i == j):
continue
if isPalindrome3(firstword + secondword):
output.append([i, j])
return output

```
##### hash表：

1. 当前单词比要拼接的单词长
2. 当前单词比要拼接的单词短或者相等。
```def palidromePairs(words):
output = []
word_to_index = {word: i for i, word in enumerate(words)}
for i, firstword in enumerate(words):
for j in range(len(firstword)+1):
x_reversed = firstword[j:][::-1]
rest = firstword[0:j]
if isPalindrome(rest) and x_reversed in word_to_index and word_to_index[x_reversed] != i:
output.append([word_to_index[x_reversed], i])

if j == len(firstword): continue
x_reversed = firstword[:j][::-1]
rest = firstword[j:]
if isPalindrome(rest) and x_reversed in word_to_index and word_to_index[x_reversed] != i:
output.append([i, word_to_index[x_reversed]])
return output

```

#### 参考及引用

https://fizzbuzzed.com/top-interview-questions-5/

Photo by Josh Sorenson from Pexels