Python算法题----取出最长回文子串

78788909

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

穷举法
取出所有的子串组合，挨个判断，返回最长的

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

class Solution(object):                 def isPalindrome(self, s, start, end):         while start < end:             if s[start] != s[end]:                 return False             start += 1             end -= 1         return True               def longestPalindrome(self, s):         """         :type s: str         :rtype: str         """         max, left, right = 0, 0, 0         for i in range(len(s)):             j = i+1             while j < len(s):                 if self.isPalindrome(s, i, j):                     if (j-i+1) > max:                         left, right = i, j                         max = j - i + 1                 j += 1         print left, right, max         return s[left:right+1]

双指针两边扩展
遍历指针为i， j=i+1， i左移，j右移。判断是否相等将长度，下标赋给临时变量，最后切片返回。唯一的大坑。回文字符串长度可以是奇数也可以是偶数。奇数的时候，内层循环从i-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 25 26 27 28 29 30 31 32 33 34 35 36 37 38

class Solution(object):               def longestPalindrome(self, s):         """         :type s: str         :rtype: str         """         n = len(s)         maxL, maxR, max = 0, 0, 0         for i in range(n):             # 长度为偶数的回文字符串             start = i             end = i + 1             while start >= 0 and end < n:                 if s[start] == s[end]:                     if end - start + 1 > max:                         max = end - start + 1                         maxL = start                         maxR = end                     start -= 1                     end += 1                 else:                     break                   # 长度为奇数的回文子串             start = i - 1             end = i + 1             while start >= 0 and end < n:                 if s[start] == s[end]:                     if end - start + 1 > max:                         max = end - start + 1                         maxL = start                         maxR = end                     start -= 1                     end += 1                 else:                     break         return s[maxL:maxR+1]