LeetCode _5

链接： 最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

输入: "cbbd"
输出: "bb"

代码：
方法一：

class Solution:
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        start = end = 0
        for i in range(len(s)):                   # 遍历s，以每个字符为中心向两边扩散
            len1 = self.centerexpand(s, i, i)     # 回文串长度为奇数，aba
            len2 = self.centerexpand(s, i, i+1)   # 回文串长度为偶数，abba
            maxlen = max(len1, len2)              

            if maxlen > end - start + 1:          # 判断是否是最长的一个回文子串
                start = i - (maxlen - 1)//2
                end = i + maxlen//2
        return s[start: end+1]                    # eg: s[0:1]输出s[0]
                
    def centerexpand(self,s,l,r):
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1
            r += 1
        return r - l - 1        #返回子串长度

方法二：

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if s == "": 
            return s
        dic = {}
        loc = [0, 0]
        ans = s[0]
        for i in range(len(s)):
            if s[i] in dic:
                keys = dic.get(s[i])
                for j in range(len(keys)):
                    start = keys[j]
                    if (i - start) > (loc[1] - loc[0]):
                        temp = s[start : i + 1]
                        if temp == temp[ : : -1]:
                            loc = [start, i]
                            break;
            dic.setdefault(s[i], []).append(i)
        return s[loc[0] : loc[1] + 1]