首页 > 代码库 > Leetcode #5. Longest Palindromic Substring

Leetcode #5. Longest Palindromic Substring

2024-08-26 22:01:11   219人阅读

Q: Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring. 
 
1. For each element in the array, use it as center to expand until it is not palindromic. 
2. Use two pointers to locate the start and end of the palindromic substring.
3. Pay attention to the odd and even case 

 1 class Solution(object):
 2     def longestPalindrome(self, s):
 3         """
 4         :type s: str
 5         :rtype: str
 6         abccba abcba
 7         """
 8 
 9         n = len(s)
10         start = end = 0
11         for i in range(n):
12             len1 = self.range(s, i, i)
13             len2 = self.range(s, i, i + 1)
14             maxLen = max(len1, len2)
15 
16             if maxLen > end - start:
17                 end = i + (maxLen) / 2
18                 start = i - (maxLen - 1) / 2
19 
20         return s[start:end + 1]
21 
22     def range(self, s, l, r):
23         while l >= 0 and r < len(s) and s[l] == s[r]:
24             l -= 1
25             r += 1
26         return r - l - 1

 

Leetcode #5. Longest Palindromic Substring


联系
我们