1. # 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
    2. #
    3. #  示例 1：
    4. #
    5. #  输入: "babad"
    6. # 输出: "bab"
    7. # 注意: "aba" 也是一个有效答案。
    8. #
    9. #
    10. #  示例 2：
    11. #
    12. #  输入: "cbbd"
    13. # 输出: "bb"
    14. #
    15. #  Related Topics 字符串 动态规划
    16. #  👍 2558 👎 0
    19. # leetcode submit region begin(Prohibit modification and deletion)
    20. class Solution(object):
    21.     def longestPalindrome(self, s):
    22.         """
    23.         :type s: str
    24.         :rtype: str
    25.         """
    26.         max_l = 0
    27.         res = ""
    28.         for i in range(0, len(s)):
    29.             # s[i] 为中心
    30.             left, right = i, i
    31.             while left >= 0 and right < len(s) and s[left] == s[right]:
    32.                 if max_l < right - left + 1:
    33.                     max_l = right - left + 1
    34.                     res = s[left:right + 1]
    35.                 left -= 1
    36.                 right += 1
    37.             # s[i] s[i+1] 为中心
    38.             left, right = i, i + 1
    39.             while left >= 0 and right < len(s) and s[left] == s[right]:
    40.                 if max_l < right - left + 1:
    41.                     max_l = right - left + 1
    42.                     res = s[left:right + 1]
    43.                 left -= 1
    44.                 right += 1
    45.         return res
    48. # leetcode submit region end(Prohibit modification and deletion)
    49. s = Solution()
    50. print(s.longestPalindrome("babad"))
    51. print(s.longestPalindrome("cbbd"))
    1. class Solution(object):
    2.     def longestPalindrome(self, s):
    3.         """
    4.         :type s: str
    5.         :rtype: str
    6.         """
    7.         start, end = 0, 0
    8.         for index, item in enumerate(s):
    9.             left1, right1 = self.expandAroundCenter(s, index, index)
    10.             left2, right2 = self.expandAroundCenter(s, index, index + 1)
    11.             if right1 - left1 > end - start:
    12.                 start, end = left1, right1
    13.             if right2 - left2 > end - start:
    14.                 start, end = left2, right2
    15.         return s[start: end + 1]
    17.     def expandAroundCenter(self, s, left, right):
    18.         while left > 0 and right < len(s) and s[left] == s[right]:
    19.             left -= 1
    20.             right += 1
    21.         return left + 1, right - 1