5. Longest Palindromic Substring

2019-03-28

5. Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

1
2
3
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

1
2
Input: "cbbd"
Output: "bb"

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        # short string
        size = len(s)
        if size == 1:
            return s
        if size == 2:
            if s[0] == s[1]:
                return s
            return s[0]
        # long string
        maxp = 1
        # empty result string
        ans = s[0]
        i = 0
        # travlsal s
        while i < size:
            j = i + 1
            # judge if two nearly char  equal
            while j < size:  #size=5
                if s[i] == s[j]:#s[0]=a s[1]=a ->j=2 ->s[0]=a s[2]=b ->break
                    j += 1
                else:
                    break
            k = 0
            # speard s from s[i]
            while i - k - 1 >= 0 and j + k<= size - 1:#(i=1)-k-1=0=0 (j=2)+0=2<(size=5)
                # not eaual and break
                if s[i- k - 1] != s[j + k]:#s[i-k-1]=a s[j+k]=b ->break
                    break
                # eaual and continue
                k += 1  #k=1
            if j - i + 2*k > maxp:  #j-i+2*k=2-0+2*1=0<mxp=1
                maxp = j- i + 2*k   
                ans = s[i - k:j + k]
            if j + k == size - 1: #2+1=3!=5
                break
            i = j       #i=2
        return ans
-->