ciid室内设计协会/深圳seo论坛

问题背景

回文串 正着读和反着读都一样的字符串，如xyx和xyyx
问题 给定一个字符串s，找s中的最长回文子串
如s = ‘asdfxxyxxhjkl’，其最长回文子串是’xxyxx’

思路

从中间开始向两边扩散

举个栗子

如 s = 'abcxyxsed'，可以看到存在的最长回文子串是'xyx'，遍历字符串s
i = 0，s[i] = 'a'，向两边扩，左边已是边界，无法进行，往后遍历
i = 1，s[i] = 'b'，向两边扩，s[i-1]!=s[i+1]，以s[i]为中心的子串不是回文串，往后遍历
i = 2，s[i] = 'c'，向两边扩，s[i-1]!=s[i+1]，以s[i]为中心的子串不是回文串，往后遍历
i = 3，s[i] = 'x'，向两边扩，s[i-1]!=s[i+1]，以s[i]为中心的子串不是回文串，往后遍历
i = 4，s[i] = 'y'，向两边扩，s[i-1]=s[i+1]，以s[i]为中心的长度为3的串是回文串，继续往外扩，可能能找到更长的回文子串，s[i-2]!=s[i+2]，没有找到更长的，现在找到了一个回文子串，但是不知道这个串是不是最长的，继续往后遍历
i = 5，s[i] = 'x'，向两边扩，s[i-1]!=s[i+1]，以s[i]为中心的子串不是回文串，往后遍历
……

一直遍历到最后，都没有再找到其他的回文子串了，可知i=4时找到的即是最长，返回结果；若是后续又找到了其他的子串，需比较二者的长度大小，选最大的返回。

刚刚说的是回文串长度是奇数的情况，对于回文串长度是偶数的情况，如‘abxyyxcd’，再用上述方法就不行了，所以

再举个栗子

如s = 'abcxyyxsed'，可以看到存在的最长回文子串是'xyyx'，遍历字符串s
i = 0, j = i+1 = 1,s[i] = 'a' ,s[j] = 'b', s[i] != s[j] ，以s[i],s[j]为中心的子串不是回文串，往后遍历
i = 1, j = i+1 = 2,s[i] = 'b' ,s[j] = 'c', s[i] != s[j] ，以s[i],s[j]为中心的子串不是回文串，往后遍历
i = 2, j = i+1 = 3,s[i] = 'c' ,s[j] = 'x', s[i] != s[j] ，以s[i],s[j]为中心的子串不是回文串，往后遍历
i = 3, j = i+1 = 4,s[i] = 'x' ,s[j] = 'y', s[i] != s[j] ，以s[i],s[j]为中心的子串不是回文串，往后遍历
i = 4, j = i+1 = 5,s[i] = 'y' ,s[j] = 'y', s[i] = s[j] ，以s[i],s[j]为中心的长度为1的子串是回文串，继续往外扩，可能能找到更长的回文子串，s[i-1] = s[j+1]，以s[i],s[j]为中心的长度为2的子串是回文串，继续往外扩，s[i-2]!=s[j+2]，没有找到更长的，现在找到了一个回文子串，但是不知道这个串是不是最长的，继续往后遍历
i = 5, j = i+1 = 6,s[i] = 'y' ,s[j] = 'x', s[i] != s[j] ，以s[i],s[j]为中心的子串不是回文串，往后遍历
……

一直遍历到最后，都没有再找到其他的回文子串了，可知i=4时找到的即是最长，返回结果；若是后续又找到了其他的子串，需比较二者的长度大小，选最大的返回。

上面罗里吧嗦讲了一大通，只是辅助理解，代码实现如下：

代码

# 找s中的最长回文子串
def longestPalindrome(s):res = ""for i in range(len(s)):# 找以s[i]为中心的最长回文子串s1 = palindrome(s,i,i)# 找以s[i],s[i+1]为中心的最长回文子串s2 = palindrome(s,i,i+1)# 比较已找到的回文子串的长度，保留最长的res = res if len(res)>len(s1) else s1res = res if len(res)>len(s2) else s2return res# 找s中的以l,r为中心的最长回文子串
def palindrome(s,l,r):while l >= 0 and r<len(s) and s[l] == s[r]:l -= 1r += 1return s[l+1:r]print(longestPalindrome("aaacdxxyxxcaa"))# 最后结果当然是
# xxyxx