5.Longest Palindromic Substring.md

题目

给定一个字符串s，找到最长回文子字符串s。假设s的最大长度为s。

举例1：

输入："babad"
输出："bab"
注意："aba"也是一个有效结果。

举例2：

输入："cbbd"
输出："bb"

思路

可以使用中心扩展的方法，把给定的每一个字母当做中心，向两边扩展，这样找到最长的子回文串。算法复杂度为O(N^2)。 分为两种情况：

• aba，这样长度为奇数的回文
• abba，这样长度为偶数的回文

代码

基本方法：

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        length = len(s)
        maxlength = 1
        start = 0
        if length == 0: return None
        if length == 1: return True

        #奇数回文
        for i in range(length):		
            j = i - 1
            k = i + 1
            while j >= 0 and k < length and s[j] == s[k]:
                if k - j + 1 > maxlength:
                    maxlength = k - j + 1
                    start = j
                j -= 1
                k += 1

        #偶数回文
        for i in range(length):
            j = i
            k = i + 1
            while j >= 0 and k < length and s[j] == s[k]:
                if k - j + 1 > maxlength:
                    maxlength = k - j + 1
                    start = j 
                j -= 1
                k += 1

        if maxlength > 0:
            return s[start:start+maxlength]
        return None

改进方法：

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if len(s)==0:
            return 0
        maxLen=1
        start=0
        for i in range(len(s)):
            if i-maxLen >=1 and s[i-maxLen-1:i+1]==s[i-maxLen-1:i+1][::-1]:
                start=i-maxLen-1
                maxLen+=2
                continue

            if i-maxLen >=0 and s[i-maxLen:i+1]==s[i-maxLen:i+1][::-1]:
                start=i-maxLen
                maxLen+=1
        return s[start:start+maxLen]