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:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example:
Input: "cbbd"
Output: "bb"
Solution: Brute Force
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
min_low = max_high = 0
for idx in xrange(len(s) - 1):
for low, high in (idx, idx), (idx, idx + 1):
low, high = self.expand_palindrome(s, low, high)
if high - low > max_high - min_low:
min_low, max_high = low, high
return s[min_low: max_high + 1]
def expand_palindrome(self, s, low, high):
while 0 <= low <= high < len(s) and s[low] == s[high]:
low -= 1
high += 1
return low + 1, high - 1
Lessons:
- Use each position as the center of a palindrome, expand it as wide as possible.
- This is faster than using each position as one edge of a palindrome, and shrink it to find the largest one.