文章作者：Tyan
博客：noahsnail.com | CSDN | 简书
1. Description
Palindrome Pairs
2. Solution
解析：Version 1简单，容易理解，但超时。Version 2是将字符串分为两部分，前半部分和后半部分，如果两部分有一部分是回文子串，则寻找另一部分的对应的回文字符串。
- Version 1
class Solution:
def palindromePairs(self, words):
result = []
length = len(words)
for i in range(length):
for j in range(i + 1, length):
positive = words[i] + words[j]
reverse = words[j] + words[i]
if self.checkPalindrome(positive):
result.append([i, j])
if self.checkPalindrome(reverse):
result.append([j, i])
return result
def checkPalindrome(self, word):
i = 0
j = len(word) - 1
while i < j:
if word[i] != word[j]:
return False
i += 1
j -= 1
return True
- Version 2
class Solution:
def palindromePairs(self, words):
result = []
stat = {}
for index, word in enumerate(words):
stat[word] = index
for index, word in enumerate(words):
length = len(word)
if length == 1 and '' in stat:
result.append([index, stat['']])
result.append([stat[''], index])
continue
for i in range(length + 1):
prefix = word[:i]
rest = word[i:]
reverse = rest[::-1]
if self.checkPalindrome(prefix):
if reverse in stat and index != stat[reverse]:
res = [stat[reverse], index]
if res not in result:
result.append(res)
suffix = word[i:]
rest = word[:i]
reverse = rest[::-1]
if self.checkPalindrome(suffix):
if reverse in stat and index != stat[reverse]:
res = [index, stat[reverse]]
if res not in result:
result.append(res)
return result
def checkPalindrome(self, word):
i = 0
j = len(word) - 1
while i < j:
if word[i] != word[j]:
return False
i += 1
j -= 1
return True
