LeetCode-5 - Longest Palindromic

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.

Solution1
很容易想到的方法，两层循环遍历整个字符串，每个可能的子串都被判定是否为回文，然后找到长度最大的子串即可。

此算法的复杂度为O(n2)

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        maxstr = ""
        for i in range(len(s)):
            for j in range(i, len(s) + 1):
                if self.isPalindrome(s[i:j]):
                    if j - i > len(maxstr):
                        maxstr = s[i:j]
        return maxstr
                        
   
    def isPalindrome(self, astr):
        if len(astr) <= 1:
            return True
        else:
            return self.isPalindrome(astr[1:-1]) if astr[0] == astr[-1] else False

Solution2

思路：
此处需要转换思路，将回文字串的特性理解得更加清楚。

1. 回文字串的特性是顺序/倒序结果一致，但是仔细考虑，分为两种：第一种是同一字符的不断重复，第二种为顺序/倒序结果的比对
2. 如果找到一个回文字串，它的长度记录为maxLen，那么下一个最长的回文字串，要么为maxLen + 1，要么为maxLen + 2
   举例说明：bbacdca，从左到右遍历整个字串，其中b为最开始的回文字串，长度为1，bb为次之的回文字串，长度为2，cdc为再之后的回文字串，长度为3，acdca为最后找到的回文字串，长度为5。
3. 由此可以看到，长度为5的回文字串，必然包括长度为3的回文字串。所以长度相邻的回文字串的长度差最大为2，最小为0，即[0,1,2]
4. 对于此处解max值的问题，[0,1,2]中可以不用考虑0，只需要考虑[1,2]长度的增加即可

此算法只遍历一次字符串，因此复杂度仅为O(n)

class Solution:
    # @return a string
    def longestPalindrome(self, s):
        if len(s)==0:
            return 0
        maxLen=1
        start=0
        for i in xrange(len(s)):
            if i-maxLen >=1 and s[i-maxLen-1:i+1]==s[i-maxLen-1:i+1][::-1]:
                start=i-maxLen-1
                maxLen+=2
                continue

            if i-maxLen >=0 and s[i-maxLen:i+1]==s[i-maxLen:i+1][::-1]:
                start=i-maxLen
                maxLen+=1
        return s[start:start+maxLen]