Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

题意

找出一个字符串的最长回文子串

思路

1. 暴力，二重循环确定子串范围。

class Solution:
    def longestPalindrome1(self, s):
        if len(s) <= 1:
            return s
        max_len = 0
        result = ""
        for i in range(len(s)):
            for j in range(i + 1, len(s)):
                if s[i:j+1] == s[i:j+1][::-1]:
                    if j - i > max_len:
                        result = s[i:j+1]
                        max_len = j - i
        if result == "":
            result = s[0]
        return result

可以看到时间复杂度也非常高

2. 中心扩展
   以一个字符为中心，向左右两边扩展。

  def longestPalindrome2(self, s):
        str_len = len(s)
        if str_len <= 1:
            return s
        start = 0
        end = 0
        for i in range(str_len -1):
            len1 = self.expendAroundCenter(s, i, i)
            len2 = self.expendAroundCenter(s, i, i+1)
            length = max(len1, len2)
            if length > (end - start):
                start = i - int((length-1)/2)
                end = i + int(length/2) + 1
        return s[start:end]
    def expendAroundCenter(self, s, left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return right - left - 1

3. 动态规划
   建立len(s) * len(s) 的矩阵dp，令dp[i][j]表示s[i:j]是否是回文子串，有以下3种情况：

• i=j 时， 任何字符本身都是回文；
• j-i<3 时，s[i]==s[j]时，是回文子串，如aa和aba；

• j-i >=3时，s[i]==s[j]
  所以状态转移方程为

  
  
  

  需要注意的点是，因为要访问dp[i+1][j-1]，因此 i 是从大到小的，j是从小到大的。

    def longestPalindrome3(self, s):
        str_len = len(s)
        if str_len <= 1:
            return s
        dp = [[False]*str_len for _ in range(str_len)]

        left = 0
        right = 0

        for i in range(str_len-1, -1, -1):
            dp[i][i] = True
            for j in range(i+1, str_len):
                dp[i][j] = s[i] == s[j] and (j-i < 3 or dp[i+1][j-1])

                if dp[i][j] and j - i > right - left:
                    left = i
                    right = j

        return s[left:right+1]

参考

https://blog.csdn.net/daidaineteasy/article/details/86238047