# LeetCode-Palindrome Pairs  Solution
Date: 2021-04-01


#### **问题**

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

时间复杂度O(nk^2)

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

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

![ - /a \c \e \c \a \b b/ $1 \b \c $2/ \b \a $3 $0 ](https://fizzbuzzed.com/assets/img/palindromepairstrie2.svg)

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 = []
    def addWord(self, word, index):
        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):
        trie.addWord(word, i)
    return trie
```

##### **穷举：**

直接两层循环即可O(n^2k)

```
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表：**

思路和Trie是一致的只是单词是逆序存放到到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](https://www.pexels.com/@joshsorenson?utm_content=attributionCopyText&utm_medium=referral&utm_source=pexels)** from **[Pexels](https://www.pexels.com/photo/scenic-view-of-sea-at-sunset-258206/?utm_content=attributionCopyText&utm_medium=referral&utm_source=pexels)**