LintCode 200. 最长回文子串
题目描述
给出一个字符串（假设长度最长为1000），求出它的最长回文子串，你可以假定只有一个满足条件的最长回文串。
测试样例
输入:"abcdzdcab"
输出:"cdzdc"
输入:"aba"
输出:"aba"
解题思路与方法
1、暴力搜索
i). 将输入字符串s逆序反转的到s1，比如abcde则变为edcba；
ii). 依次遍历输入字符串s的每一个字符的位置，将其作为起始位i。每次固定i，然后从i开始依次遍历至字符串s的最后一个位置，将其作为终止位j。在这期间每遍历一个j便判断从i到j的子串是否出现在s1中，从而确定从i到j的子串是否回文；
iii). 若s中从i到j的子串是回文，则比较这个回文子串与之前获得的最长回文子串的长度；若当前回文子串的长度大，则更新获得的最长回文子串长度，同时记录下最长回文子串的起止位置i、j；
iv). 重复ii)和iii)直至将i遍历完s的所有字符位置
2、动态规划
i). 建立一个2维数组，用于记录从位置i到位置j是否是回文子串（O()的空间复杂度）；
ii). 依次遍历输入字符串s的每个位置，将其作为终止位right；然后从right开始向左边遍历每个位置，将其作为起始位置left，直至s的第一个字符位置；
iii). 当left和right相邻或者两者之间的子串是回文，并且当前left和right位置的字符相等，那么更新2维数组，记录下从位置left到位置right是回文子串。同时，比较该回文子串与之前获得的最长回文子串的长度，若当前较大，则更新最长回文子串长度，同时记录下最长回文子串的起始位置分别为left和right；
iv). 重复ii)和iii)，直至right遍历完s的所有字符位置
3、有点暴力的中线扩充
i). 依次遍历输入字符串s的每个位置i，从i出发向左右两边扩充，获得left和right两个位置；
ii). 同时，从i和i右边的一个位置j出发，分别向左和向右（i向左、j向右）扩充，获得left和right两个位置；
iii). 在i)和ii)中，分别进入循环，对于每个left-right对，当它们都位于s中的有效位置且当前位于left和right的字符相等时，left和right就分别向左和向右移动，直至left和right有其一走到了s的有效位置之外或者left与right位置上的字符不相等，则跳出循环；
iv). 跳出循环后，比较left和right之间的回文子串长度与之前获得的最长回文子串长度，若当前较大，则更新这个长度，同时记录下这个最长回文子串；
v). 重复i)、ii)、iii)直至遍历完s中的所有位置
代码
1、暴力搜索
class Solution:
"""
@param s: input string
@return: the longest palindromic substring
"""
def longestPalindrome(self, s):
# write your code here
if not s:
return ""
if len(s) == 1:
return s
# 记录最长回文子串的长度
longest_len = 0
# 最长回文子串的起止，
# 其中right是excluded，即[left, right)
left = right = 0
# 将字符串反转
inverted_s = s[::-1]
for i in range(len(s)):
# 注意j要到len(s)，这样才可能取到最后一个字符
for j in range(i + 1, len(s) + 1):
if s[i:j] in inverted_s and len(s[i:j]) > longest_len:
left = i
right = j
longest_len = len(s[i:j])
return s[left:right]
2、动态规划
class Solution:
"""
@param s: input string
@return: the longest palindromic substring
"""
def longestPalindrome(self, s):
# write your code here
if not s:
return ""
if len(s) == 1:
return s
# 最长回文子串的头尾字符
# 其中tail是included
head = tail = 0
# 记录最长回文子串的长度
longest_len = 0
# 记录从第i个字符到第j个字符是否是回文
is_palindrome = [[False] * len(s) for _ in range(len(s))]
for right in range(len(s)):
for left in range(right, -1, -1):
if (right - left < 2 or is_palindrome[left + 1][right - 1]) \
and s[left] == s[right]:
is_palindrome[left][right] = True
cur_len = right - left + 1
if cur_len > longest_len:
head = left
tail = right
longest_len = cur_len
return s[head:tail + 1]
3、中线扩充
class Solution:
"""
@param s: input string
@return: the longest palindromic substring
"""
longest_palindrome = ''
def longestPalindrome(self, s):
# write your code here
if not s:
return ""
if len(s) == 1:
return s
for start in range(len(s)):
# 从start位置向两边扩展判断是否最长回文子串
self.find_longest_palindrome(s, start, start)
# 从start和start+1位置向两边扩展判断是否最长回文子串
self.find_longest_palindrome(s, start, start + 1)
return self.longest_palindrome
def find_longest_palindrome(self, s, left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
# 注意跳出循环后left是在回文子串的第一个字符的左边一个位置
# right是在回文子串最后一个字符的右边一个位置
if right - left - 1 > len(self.longest_palindrome):
self.longest_palindrome = s[left + 1:right]
