【leetcode刷题】20T4-最长回文子串

• 2020 年 2 月 16 日
• 筆記

木又同学2020年第4篇解题报告

leetcode第5题：最长回文子串

https://leetcode-cn.com/problems/longest-palindromic-substring/

【题目】

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

示例 1：  输入: "babad"  输出: "bab"  注意: "aba" 也是一个有效答案。    示例 2：  输入: "cbbd"  输出: "bb"  

【思路】

首先想到的还是暴力破解，对每个子串，判断是否为回文子串，得到子串的复杂度为O(n^2)，判断回文子串的复杂度为O(n)，因此总的时间复杂度为O(n ^ 3)。很抱歉，没通过所有case。

我们找找回文串的特点，是不是存在一个或者两个中间元素，然后其往前和往后的字符依次相等，可以概括为“aba”和“abba”两种模式。

那么，我们可以先找中心点，再判断两边元素是否相等。判断时，如果相同offset前后两边元素相等，则判断下一个offset前后两边元素是否相等，并更新结果；如果不相等，则continue，对下一个中心点进行相同操作。

【代码】

python版本

class Solution(object):      def longestPalindrome(self, s):          """          :type s: str          :rtype: str          """          if len(s) == 0:              return ""          res = s[0]          '''          # 暴力破解，超时！          for i in range(len(s)):              for j in range(i+1, len(s)):                  tmp = s[i:j+1]                  if tmp == tmp[::-1] and j-i+1 > len(res):                      res = tmp          return res          '''          # 每个点为中心发散          for i in range(len(s)):              # "aba"类型              j = 1              while i-j >= 0 and i+j < len(s):                  if s[i-j] != s[i+j]:                      break                  if 2*j+1 > len(res):                      res = s[i-j: i+j+1]                  j += 1                # "abba"类型              j = 0              while i-j >= 0 and i+j+1 < len(s):                  if s[i-j] != s[i+j+1]:                      break                  if 2*j+2 > len(res):                      res = s[i-j: i+j+2]                  j += 1          return res