leetcode_5

Posted on | In

[LeetCode: No.5]

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

1
2
3
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

1
2
Input: "cbbd"
Output: "bb"

最长回文子串的中间子串也是回文串，换言之，回文串是否最长，可以看回文串两边的字符是否相同。例如“dabcba”的最长回文子串是“abcba”，其可看出回文子串“bcb”的拓展，判断“bab”两边的字符是否相同决定是否进行回文子串拓展（可以利用切片的索引左右移动实现）

由这个想法下， 写出第一个代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if len(s) < 2:
            return s
        self.res = ""
        for i in range(len(s)):
            left = right = i
            while left>=0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            if right -left -1 > len(self.res):
                self.res = s[left+1:right]
        return self.res

其中在While语句中， s[left] == s[right]是一定要放在最后面的，因为在python中and的机制是这样的and之前的是Flase， 那么and后面的就不会被执行，有可能会出现left=-1或者right=len(s)，这是的s[left]和s[right]会超出索引值。还有就是一定要注意字符串的索引值和长度。

但是这段代码还是会出错，当输出值s为’abbc’是 ，检测不出bb，因为他没有对称中心。所以我们在做添加，left和right的初始值不设为想等而是相差1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """      
        if len(s) < 2:
            return s
        self.res = ""
        for i in range(len(s)):
            #这里就是考虑到两种情况，从相同字符拓宽和从相邻字符拓宽
            self.helper(s, i, i)
            self.helper(s, i, i+1)
        return self.res
    
    def helper(self,s, left, right):
        #这里是判断当前回文子串两端相同的时候，向两端拓展
        while left>=0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
            #这里的right-left-1是当前的回文子串长度，大于历史最大值，就更新最大值
        if right -left -1 > len(self.res):
            self.res = s[left+1:right]