正文
[Leetcode] 336. Palindrome Pairs_Hard
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
Given a list of unique words, find all pairs of distinct indices (i, j) in the given list, so that the concatenation of the two words, i.e. words[i] + words[j] is a palindrome.
Example 1:
Given words = ["bat", "tab", "cat"]
Return [[0, 1], [1, 0]]
The palindromes are ["battab", "tabbat"]
Example 2:
Given words = ["abcd", "dcba", "lls", "s", "sssll"]
Return [[0, 1], [1, 0], [3, 2], [2, 4]]
The palindromes are ["dcbaabcd", "abcddcba", "slls", "llssssll"]
这道题的思路就是把每个word和index存到diction里面, 然后针对每个word, for loop, 拆分为两部分, 如果前面部分是palindrome, 那么把后面部分的单词reverse, 如果reverse后的单词在diction里面, ans.append(d[back], index); 同理, 如果后面部分是palindrome, 把前面部分的单词reverse, 如果reverse后的单词在diction里面, ans.append(index, d[back]). 此时需要注意的是在后面check的时候就不要考虑整个单词reverse的情况, 因为前面单词reverse的时候已经考虑到了. 如果不明白的话就用set去去重, 最保险的做法.
参考Solution.
class Solution(object):
def palindromePairs(self, words):
"""
:type words: List[str]
:rtype: List[List[int]]
"""
def checkpal(w):
return w == w[::-1] # 反正O(n), 所以用最粗暴的方式 d, ans = {w:index for index, w in enumerate(words)},[]
for word, index in d.items():
l = len(word)
for i in range(l+1): # l+1 因为pref要到[:l]
pref = word[:i]
suf = word[i:]
if checkpal(pref):
back = suf[::-1]
if back != word and back in d:
ans.append([d[back], index]) if i != l and checkpal(suf): # delete the duplicates
back = pref[::-1]
if back != word and back in d:
ans.append([index, d[back]])
return ans
