“This is the third day of my participation in the November Gwen Challenge. See details of the event: The last Gwen Challenge 2021”.

LeetCode 200 simple questions

Topic describes

Given a string s, find the longest substring in s.

Example 1:

Input: s = “babad” Output: “bab” Explanation: “ABA” is also the answer to the question.

Example 2:

Input: s = “CBBD” Output: “bb”

Example 3:

Input: s = “a” Output: “a”

Example 4:

Input: s = “AC”

prompt

  • 1 <= s.length <= 1000
  • sConsists of only numbers and English letters (uppercase and/or lowercase)

Their thinking

The brute force method is always the simplest solution, but it is not always speedy. The two-level for loop iterates through all cases to find the largest substring of the loop. Display timeout when code is submitted. This is very uncomfortable!

class Solution(object) :
    def longestPalindrome(self, s) :
        """ :type s: str :rtype: str """
        length = len(s)
        # use the first character as the initial value of max_str
        max_str = s[0]
        for i in range(length - 1) :for j in range(i + 1, length):
            	If s[I: j + 1] is a subroutine and its length is greater than len(max_str), replace it
                if s[i: j + 1] == s[i: j + 1] [: : -1] and j - i + 1 > len(max_str):
                    max_str = s[i: j + 1]
        return max_str
Copy the code

Time complexity: O(n³) Space complexity: O(1)

2. Center diffusion Method According to the symmetry of the palindrome string, we can specify its center for circulation, and judge whether the left and right characters are equal each time.

class Solution(object) :
    def expandAroundCenter(self, s, left, right) :
        max_len = 0
        # Exit condition: Out of bounds
        while left >= 0 and right < len(s):
            if s[left] == s[right]:
                left -= 1
                right += 1
            else:
                break
        return right - left - 1


    def longestPalindrome(self, s) :
        """ :type s: str :rtype: str """
        rst = s[0]
        # Traverse the center point
        for i in range(len(s) - 1) :Get the maximum palindrome length from expandAroundCenter
        	# odd, left = right = I
            odd_len = self.expandAroundCenter(s, i, i)
            # even, left = I, right = I + 1
            even_len = self.expandAroundCenter(s, i, i + 1)
            Get maximum len
            max_len = max(odd_len, even_len)
            if max_len > len(rst):
            	Get the starting index of the palindrome string
                begin = i - (max_len - 1) / /2
                rst = s[begin: begin + max_len]
        return rst
Copy the code

Time complexity: O(n²) Space complexity: O(1)

Clocked in today, the current progress is 8/200.