Leetcode 336. Palindrome Pairs

文章作者:Tyan
博客:noahsnail.com  |  CSDN  |  简书

1. Description

Palindrome Pairs

2. Solution

解析:Version 1简单,容易理解,但超时。Version 2是将字符串分为两部分,前半部分和后半部分,如果两部分有一部分是回文子串,则寻找另一部分的对应的回文字符串。

  • Version 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
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

Reference

  1. https://leetcode.com/problems/palindrome-pairs/
如果有收获,可以请我喝杯咖啡!