回文对

1.问题描述

给出一个单词列表，在给定列表中查询所有的不同的索引 （i，j)回文串构成回文串，words[i]+words[j]

2.问题例子

给出words=['bat','tab','cat'] 返回 【0，1】，【1，0】回文串为【battab】 【tabbat】

给出words=['abcd','dcba','lls','s','sssll'] 返回【0，1】，【1，0】，【3，2】，【2，4】

abcddcba,dcbaabcd,slls,llssssll

3代码

class huiwen: def palindromePairs(self, words): if not words: return [] table= dict() for idx, word in enumerate(words): table[word]=idx ans=[] for idx,word in enumerate(words): size=len(word) for i in range(size+1): leftSub= word[:i] rightSub=word[i:] if self.isPalindrome(leftSub): reversedRight=rightSub[::-1] if reversedRight in table and table[reversedRight] != idx: ans.append([table[reversedRight],idx]) if len(reversedRight)>0 and self.isPalindrome(rightSub): reversedLeft= leftSub[::-1] if reversedLeft in table and table[reversedLeft] != idx: ans.append([idx,table[reversedLeft]]) return ans def isPalindrome(self,word): if not word: return True left=0 right=len(word)-1 while left <= right: if word[left] != word[right]: return False left +=1 right -=1 return True if __name__=='__main__': words=['bat','tab','cat'] y=huiwen() print("1.输入的数组为：",words) print("1.输出的数组为：",y.palindromePairs(words)) words=['abcd','dcba','lls','s','sssll'] print("2.输入的数组为：",words) print("2.输出的数组为：",y.palindromePairs(words)) words=['apple','hello','words','word','olleh','elppa'] print("3.输入的数组为：",words) print("3.输出的数组为：",y.palindromePairs(words))

运行结果为：

1.输入的数组为： ['bat', 'tab', 'cat'] 1.输出的数组为： [[1, 0], [0, 1]] 2.输入的数组为： ['abcd', 'dcba', 'lls', 's', 'sssll'] 2.输出的数组为： [[1, 0], [0, 1], [3, 2], [2, 4]] 3.输入的数组为： ['apple', 'hello', 'words', 'word', 'olleh', 'elppa'] 3.输出的数组为： [[5, 0], [4, 1], [1, 4], [0, 5]]