本文主要是介绍leetcode336. Palindrome Pairs，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
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”]
思路：
x+y是Palindrome Pairs的条件是：
y+xleft+xright
或者 xleft+xright+y
y==xright and xleft 回文
y==xleft and xright回文
用hash table 来求解不会TLE
注意如果x和y都是回文，取x+y
class Solution(object):def palindromePairs(self, words):dic={}for i in range(len(words)):dic[words[i]]=iret=[]for i in range(len(words)):x=words[i]for j in range(len(words[i])+1):left=x[:j]right=x[j:]flag=dic.get(left[::-1])if flag!=None and right==right[::-1] and flag!=i:ret.append([i,flag])flag=dic.get(right[::-1])if flag!=None and left==left[::-1] and flag!=i and j!=0:ret.append([flag,i])return ret这篇关于leetcode336. Palindrome Pairs的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
