Longest Palindromic Substring – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem – Longest Palindromic Substring – Leetcode Challenge – Python Solution.
Source – qiyuangong’s repository.
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
# my solution
# expand string according to Manacher algorithm
# but extend radius step by step
ls = len(s)
if ls <= 1 or len(set(s)) == 1:
return s
# create a new list like this: "abc"->"a#b#c"
temp_s = '#'.join('{}'.format(s))
# print temp_s
tls = len(temp_s)
seed = range(1, tls - 1)
# this table stores the max length palindrome
len_table = [0] * tls
for step in range(1, tls / 2 + 1):
final = []
for pos in seed:
if pos - step < 0 or pos + step >= tls:
continue
if temp_s[pos - step] != temp_s[pos + step]:
continue
final.append(pos)
if temp_s[pos - step] == '#':
continue
len_table[pos] = step
seed = final
max_pos, max_step = 0, 0
for i, s in enumerate(len_table):
if s >= max_step:
max_step = s
max_pos = i
return temp_s[max_pos - max_step:max_pos + max_step + 1].translate(None, '#')
# def longestPalindrome(self, s):
# # example in leetcode book
# max_left, max_right = 0, 0
# ls = len(s)
# for i in range(ls):
# len1 = self.expandAroundCenter(s, i, i)
# len2 = self.expandAroundCenter(s, i, i + 1)
# max_len = max(len1, len2)
# if (max_len > max_right - max_left):
# max_left = i - (max_len - 1) / 2
# max_right = i + max_len / 2
# return s[max_left:max_right + 1]
#
# def expandAroundCenter(self, s, left, right):
# ls = len(s)
# while (left >= 0 and right < ls and s[left] == s[right]):
# left -= 1
# right += 1
# return right - left - 1
# def longestPalindrome(self, s):
# #Manacher algorithm
# #http://en.wikipedia.org/wiki/Longest_palindromic_substring
# # Transform S into T.
# # For example, S = "abba", T = "^#a#b#b#a#$".
# # ^ and $ signs are sentinels appended to each end to avoid bounds checking
# T = '#'.join('^{}$'.format(s))
# n = len(T)
# P = [0] * n
# C = R = 0
# for i in range (1, n-1):
# P[i] = (R > i) and min(R - i, P[2*C - i]) # equals to i' = C - (i-C)
# # Attempt to expand palindrome centered at i
# while T[i + 1 + P[i]] == T[i - 1 - P[i]]:
# P[i] += 1
#
# # If palindrome centered at i expand past R,
# # adjust center based on expanded palindrome.
# if i + P[i] > R:
# C, R = i, i + P[i]
#
# # Find the maximum element in P.
# maxLen, centerIndex = max((n, i) for i, n in enumerate(P))
# return s[(centerIndex - maxLen)//2: (centerIndex + maxLen)//2]
if __name__ == '__main__':
# begin
s = Solution()
print s.longestPalindrome("abcbe")
