Save you from what? My interview! (Swipe Leetcode from zero — No.005)

Write in front:

Xiaozhan this record posted fewer and fewer readers, perhaps xiaozhan summary is not good enough welcome to the message area to put forward valuable opinions! Also welcome to brush leetcode with Xiaozhan regularly, every Monday and Friday update a problem, every problem thoroughly, welcome a problem multiple solutions, looking for the best solution! This record post even if there is only one reader, xiaozhan will insist on brushing!

No.5 Maximum callback substring

原 文 : There are Chinese websites, so I don’t read English.

Such as:

# sample aInput:"babad"Output:"bab"Note:"aba"It's also a valid answer.Example # 2Input:"cbbd"Output:"bb"Copy the code

If you want to find all the existing substrings, then compare the length and output the longest substring. If you want to find the longest substring, you can find the longest substring. Start to write according to the case for the comparison, found a very key point! The middle substring of the longest palindrome string is also a palindrome string, in other words, the longest palindrome string can be determined by whether the characters on both sides of the palindrome string are the same. For example, the longest loop substring of “dabcba” is “abCBA”, which can see the expansion of the loop substring “BCB”, and determine whether the characters on both sides of “bab” are the same to determine whether to expand the loop substring (which can be achieved by moving the index of slices left and right).

Row of pit! Jen thought it was a good idea, so he implemented it. The code looks like this:

class Solution:
    def longestPalindrome(self, s):
        """ :type s: str :rtype: str """
        The single character itself is the largest string of its own
        if len(s) < 2:
            return s
        # define the string to return
        self.res = ""
        for i in range(len(s)):
            Assume each character is a palindrome character center, expand the judgment to both ends, left,right, record the left and right index of the string
            left = right = i
            If the string is the same at both ends, extend the string to both ends
            while left>=0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            # where right-left-1 is the current length of the substring, if greater than the historical maximum, update the maximum value
            if right -left -1 > len(self.res):
                self.res = s[left+1:right]
        return self.res
Copy the code

If you are interested, you can submit the code to try it out. You can only pass some of the sample tests. Why is that? Example 2 “CBBD” will be similar to this error! Find the error are analyzed, because the code above the default from the same character position to expand on both ends, however, test cases, such as the “CBBD” from adjacent position to expand two strings, so we can be both taken into account, the final choice of the longest, considering this is the same action, for clean code, Modularize it into a function as follows:

class Solution:
    def longestPalindrome(self, s):
        """ :type s: str :rtype: str """
        The single character itself is the largest string of its own
        if len(s) < 2:
            return s
        # define the string to return
        self.res = ""
        for i in range(len(s)):
            Widening from the same character and widening from adjacent characters
            self.helper(s, i, i)
            self.helper(s, i, i+1)
        return self.res
    
    # split out of the same operation function!
    def helper(self,s, left, right):
        If the string is the same at both ends, extend the string to both ends
        while left>=0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
            # where right-left-1 is the current length of the substring, if greater than the historical maximum, update the maximum value
        if right -left -1 > len(self.res):
            self.res = s[left+1:right]
Copy the code

Before we give the result, it’s worth saying a few words about self.

1. Self is not a keyword and can be replaced with something else (such as this), just the habit of using self

2. Self does not refer to the class itself, but to an instance object (e.g. Class person() a = person(‘xiaozhan’), in which case self refers to the instance object a of the person class).

The complete code results are as follows :(xiaozhan is the Chinese website to see the question, the English website to submit)

(No.001) Swipe Leetcode from zero

(No.002) Swipe Leetcode from zero

Swipe Leetcode from zero (No.003)

(No.004) Swipe Leetcode from zero

Please scan the code to follow the wechat public account, and enjoy learning and playing with Xiaozhan

​