首页 > 代码库 > longest palindromic substring

longest palindromic substring

2024-09-13 02:35:17   217人阅读

problem description:

　　given a string s, you shou find the longest palindromic substring in there

for example:
input :"ssaass"

ouput:"ssaass"

 

one solution: times o(n^2):

　　

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        length = len(s)
        i = length
        if length == 0:
            return
        while i >1:
            j = 0
            while j <= (length - i):
                s1 = s[j:j+i]
                s2 = s1[::-1]
                if s1 == s2:
                    return s1
                j += 1
            i -= 1
        return s[0]

but in the leedcode online judge, it take a long time to exceed, so it is not good enough.Then i write anothe code according to someone write in the discussion.It‘s main thought is that 

the same words(the one word also can be explainede as the same words) should be included in the center of the substring, then you can expand this substring.There should be three point. Defining i in order to limit the position of the center, it‘s length is form 0 to len-1.Defining j, k in order to record the bounds of the palindromic substring.Maybe i don‘t explain it well, so there is my code.It is written by python.

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        length = len(s)
        i = 0
        minstart = 0
        maxlen = 1
        if length <= 1:
            return s[0]
        while i< length:
            while (length - i)<maxlen/2:
                return s[minstart:minstart+maxlen]
            j = i
            k = i
            while k<(length -1) and s[k]==s[k+1]:
                k += 1
            i = k+1
            while k<(length -1) and j and s[j-1]==s[k+1]:
                j -= 1
                k += 1
            if (k - j +1)>maxlen:
                minstart = j
                maxlen = k-j+1
        return s[minstart:minstart+maxlen]

 

  

longest palindromic substring


联系
我们