LeetCode/solution/5LongestPalindromicSubstring.py at master · Alarical/LeetCode · GitHub

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
44
45
46
47
48
class Solution:
    # Expand Around Center
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        begin = 0
        res = 0  # longest length
        for i in range(len(s)):
            gap = 0
            while i - gap >= 0 and i + gap < len(s):
                if s[i - gap] == s[i + gap]:
                    if gap*2+1 > res:
                        res = gap*2+1
                        begin = i-gap
                    gap += 1
                else:
                    break
            gap = 1
            while i-gap+1 >=0 and i+gap < len(s):
                if s[i - gap+1] == s[i + gap]:
                    if gap*2 > res:
                        res = gap*2
                        begin = i-gap+1
                    gap += 1
                else:
                    break
        return s[begin : begin+res]

    # dp solution
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        dp = [[0] * len(s) for _ in range(len(s))]
        begin = 0
        res = 0
        for i in range(len(s)):
            for j in range(i+1):
                dp[j][i] = s[j] == s[i] and (i-j <= 2 or dp[j+1][i-1] == 1)
                if dp[j][i]:
                    if i-j+1 > res:
                        res = i-j+1
                        begin = j
        return s[begin:begin+res]