LeetCode-最大回文串问题


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”

方法一(穷举法):

这是我看到题目的第一想法,相当于遍历了整个字符串,然后当找到和索引i相同的索引j时,再往里面判断是否是对称

class Solution:
def longestPalindrome(self, s):
    """
    :type s: str
    :rtype: str
    """
    i = 0
    j = 1
    max1 = 1
    n = len(s)
    if n == 0:
        return s
    else:
        while i < n - 1:
            j = i + 1
            while j < n - 1:
                if s[i] == s[j]:
                    j = j + 1
                else:
                    break
            t=0
            while i-t>0 and j<=n-1 :
                if s[i-1-t] == s[j+t]:
                    t=t+1

                else:
                    break
            if j-i+t*2>max1:
                max1=j-i
                ans=s[i:j]
            i = j
        return ans

方法二(改进):

对上面的算法进行改进,利用找“核”的思想寻找回文字符串,回文字符串的两个重要“核”:aa和aba类似这样形式的字符串,利用i=j

#这样不用遍历整个字符串,先找到这样的核,再往两边判断是否对称,最后返回索引。

class Solution:
def longestPalindrome(self, s):
    """
    :type s: str
    :rtype: str
    """
    i=0
    max1=1
    n=len(s)
    ans=s[0]
    while i<n:
        j=i+1
        while j<n:
            if s[i]==s[j]:
                j=j+1
            else:
                break
        k=0
        while i-k>0 and j+k<n:
             if s[i-k-1]==s[j+k]:
                 k=k+1
             else:
                 break
        length=j-i+2*k
        if length>max1:
            max1=length
            ans=s[i-k:j+k]
        i=j
    return ans

比较
第一种方法之所以时间复杂度很大是因为两点:

1:没有利用“核”思想,遍历了整个字符串
2:第一种方法从外往里,而第二种方法是从里往外,更加符合回文字符串的特点,即对称性,节省了很多时间。

算法三

**待续