最大回文子串

题目

A palindrome is a sequence of characters that reads the same backwards and forwards. Given a string, s, find the longest palindromic substring in s.

Example:
Input: "banana"
Output: "anana"

Input: "million"
Output: "illi"

分析

由于回文字符串是对称的，比较直观的解法是，依次枚举每一个字符的位置，以当前位置作为中间点，向左右两边扩展，直到遇到不同的字符为止。

另外，需要考虑回文子串长度为偶数的特殊情况。这时候，因为中间有2个相同的字符，不太方便操作指针。可以先对原始字符串做一个预处理：即在每个位置插入一个 "#" 字符，这样，就不存在特殊性了。得到结果后，只需要对子串重新剔除掉人为插入的 "#" 字符即可。

时间复杂度为 O(n^2).

另外，还可以采用动态规划法求解，暂未花时间研究。

思路参考：https://blog.csdn.net/u013309870/article/details/70742315

代码

class Solution: 
    def longestPalindrome(self, s):
        if s == "":
            return ""
        
        # 填充
        s2 = ""
        for c in s:
            s2 += "#" + c
        s2 += "#"

        result = ""

        # 枚举每个位置，向两边扩展
        for i in range(1, len(s2)):
            word = s2[i]
            offset = 1
            while offset <= i and i + offset < len(s2):
                if s2[i - offset] == s2[i + offset]:
                    word = s2[i - offset] + word + s2[i + offset]
                else:
                    break
                offset += 1
            
            if len(word) > len(result):
                result = word
        
        # 去除 padding characters
        result2 = ""
        for i in range(1, len(result), 2):
            result2 += result[i]

        return result2
        
# Test program
s = "tracecars"
print(str(Solution().longestPalindrome(s)))
# racecar