leetcode5-- Longest Palindromic Substring

leetcode5-- 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 1:

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

Input: "cbbd"
Output: "bb"

即找出最长的回文字符串,首先是如何找到回文字符串,然后才是如何找到最长的,

找回文字符串,就是从某一个字符串开始,然后往两边扩散,看看是否满足条件,满足了就再扩散。

解法如下

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if len(s)<2:
            return s
        
        n = len(s)
        maxLen = 0
        start = 0
        
        for i in range(n-1):
            start, maxLen = self.helper(s, i,i,start, maxLen)
            start, maxLen = self.helper(s, i, i+1, start, maxLen)
            print start, maxLen
        return s[start:start+maxLen]
        

    def helper(self, s, left, right, start, maxLen):
        """
        s: 是字符串,left是这次要比较的左边的index,right是右边的index, start是最终返回的回文字符串的开始位置,maxLen是最终回文字符串的长度
        """
        while(left>=0 and right<len(s) and (s[left]==s[right])):
            left -= 1
            right += 1
            
        if (maxLen < right-left-1):
            maxLen = right-left-1   ## 更新当前的最大长度,因为上面的while结束的时候字符串应该是在[left+1, right-1]所以长度是(right-1-left-1+1).
            start = left+1            
        return start, maxLen
            
        

因为要不断地更新start和maxLen所以就返回了,如果用c++的话,可以用引用。

注意这里如果写成这样是不行的

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if len(s)<2:
            return s
        
        n = len(s)
        maxLen = 0
        start = 0
        
        for i in range(n-1):
            self.helper(s, i,i,start, maxLen)
            self.helper(s, i, i+1, start, maxLen)
            
        return s[start:start+maxLen]
        

    def helper(self, s, left, right, start, maxLen):
        while(left>=0 and right<len(s) and (s[left]==s[right])):
            left -= 1
            right += 1
            
        if (maxLen < right-left-1):
            maxLen = right-left-1
            start = left+1
            

详细解释的

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if len(s)<2:
            return s
        n = len(s)
        maxLen = 0
        start = 0
        for i in range(n-1):
            start, maxLen = self.helper(s, i, i, start, maxLen)   # 从每一个字符串出发开始找,针对的是bab这种情况
            start, maxLen = self.helper(s, i, i+1, start, maxLen)  # 针对的是noon这种情况
    
        return s[start:start+maxLen]
    
    # 因为要不断地更新start, 和maxLen 所以start, maxLen要不断地传入
    def helper(self, s, left, right, start, maxLen):
        """
        s: 字符串
        left,right都是位置
        start 是最终要返回的回文字符串的开始的位置
        maxLen 是最长的回文字符串的长度
        
        """
        # 注意是从中间往外走,
        while left>=0 and right<len(s) and s[left]==s[right]: 
            left -= 1
            right += 1
            
        # 上面结束的时候说明当前的回文截止了,要计长度 
        # [left+1, right-1]
        if maxLen < right-left-1:  # 如果之前的最大值没有现在的大的话,
            maxLen = right-left-1 # 更新最大值
            start = left + 1    # 也更新初始位置
        return start, maxLen

再理解

其实要得到最长的回文字符串,肯定是要先判断这个是不是回文字符串,然后如果这个是的话,就记录一下,然后并在每次判断的时候更新一下。 这个题的思路就是针对每一个字符,然后判断一下以当前这个字符为中心有没有可能出现回文字符串,如果有的话,就判断一下有没有必要更新一下之前最长的回文字符串的开始位置,和最大长度, 实际上start, 和 maxLen 代表的就是最长的回文字符串的开始位置和最大的长度.

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦