LeetCode-5. Longest Palindromic Substring

[ninehills]

20170716

问题

https://leetcode.com/problems/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"

思路

有O(n)的算法，以后参考：http://articles.leetcode.com/longest-palindromic-substring-part-ii/
目前看了提示后，采用下面的思路：

• 回文字符串的中心点两种『aba』以及『bb』，故可能有的回文字符串共计 2n -1个，n为字符串的长度
• 遍历字符串，对每个中心点找到其回文字符串的长度，取最大值
• 时间复杂度是O(n^2)，空间复杂度为O(1)

解答

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        longest_str = ""
        len_s = len(s)
        for index in range(len_s):
            # 以index为中心的最长回文
            l = r = index
            while (l >= 0) and (r < len_s):
                if s[l] == s[r]:
                    l = l - 1
                    r = r + 1
                    continue
                else:
                    break
            s1 = s[l+1:r]
            if len(s1) > len(longest_str):
                longest_str = s1
                
            # 以index+0.5为中心的最长回文
            l = index
            r = index + 1
            while (l >= 0) and (r < len(s)):
                if s[l] == s[r]:
                    l = l - 1
                    r = r + 1
                    continue
                else:
                    break
            if l + 1 < r and r <= len(s):
                s2 = s[l+1:r]
                if len(s2) > len(longest_str):
                    longest_str = s2
        return longest_str

print Solution().longestPalindrome('abbc')