#5 Longest Palindromic Substring——Top 100 Liked Questions

清疚 2022-02-05 13:01 216阅读 0赞

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"

> 第一次：想法是将得到s的倒序字符串s1，将s与s1对应位置的元素进行比较，并保留最大长度相同的元素。这种想法是错误的！如：cbbd与dbbc，虽然可得到bb，但对于dabab与babad而言，只能得到aba 这一种情况。

> """
> 
> 第二次：遍历s中的每个字符，以该字符为中心，寻找其最长回文字符串，对于长度为奇数的可行，为偶数的会出错，如cbbd是找不到bb的，解决方法是在字符与字符之间插入辅助字符‘\#’，包括初始位置与末尾，这样均能保证字符串长度为奇数。
> 
> """
> 
> class Solution(object):  
>     def longestPalindrome(self, s):  
>         """  
>         :type s: str  
>         :rtype: str  
>         """  
>         if len(s) == 1 or len(s) == 0: return s  
>         s = '\#' + '\#'.join(s) + '\#'  
>         print(s)  
>         ll = len(s)  
>         maxLen = 0  
>         result = \[\]  
>         for i in range(0, ll):  
>             subStr = ""  
>             for j in range(1, i + 1):  
>                 if i + j < ll and s\[i - j\] == s\[i + j\]:  
>                     pass  
>                 else:  
>                     subStr = s\[i-j+1: i+j\]  
>                     break  
>                 subStr = s\[0:2\*i+1\]  
>                   
>             if maxLen <= len(subStr):  
>                 maxLen = len(subStr)  
>                 result = subStr  
>         return result.replace('\#', '')
> 
> """
> 
> Runtime: 3080 ms, faster than 30.83% of Python online submissions forLongest Palindromic Substring.
> 
> Memory Usage: 11.7 MB, less than 29.57% of Python online submissions for Longest Palindromic Substring.
> 
> """