当前位置：网站首页>Chapter I 100 hot questions (1-5)

Chapter I 100 hot questions (1-5)

2022-06-22 19:41:00 【Fioman_ Hammer】

1. Sum of two numbers

① subject

Given an array of integers nums And an integer target value target, Please find and as the target value in the array target The two integers of , And return their array subscripts .
You can assume that each input corresponds to only one answer . however , The same element in the array cannot be repeated in the answer . You can return the answers in any order .

② Example

 Input : nums = [2,7,11,15],target = 9
 Output : [0,1]

 Input : nums = [3,2,4],target = 6
 Output : [1,2]

 Input : nums = [3,3],target = 6
 Output : [0,1]

③ answer

solution 1: Violent ergodic solution

Traversal array , According to the condition , If the conditions are met, record the number .

The first is to write a decorator for counting time , This decorator will be used in the later algorithm evaluation test :

def cout_time(func):
    def inner(*args, **kwargs):
        timeBefore = time.time()
        ret = func(*args, **kwargs)
        print(" function :{}()  Execution time consuming : {} ms".format(func.__name__, (time.time() - timeBefore) * 1000))
        return ret

    return inner

The algorithm of violent solution :

#  Violent problem solving 
@cout_time
def two_sum_01(nums, target):
    for index1, x in enumerate(nums):
        for index2, y in enumerate(nums):
            if x + y == target and index1 != index2:
                return [index1, index2]
    return []

test :

if __name__ == '__main__':
    nums = list(range(1000))
    target = 1990
    resIndex = two_sum_01(nums, target)
    print("res: {}".format(resIndex))

test result :

solution 2: solution 1 Optimized version , That is, when traversing , You don't need to traverse all of them , The first list can be traversed from scratch , Second list , Just traverse the elements after the first list , Because the previous has been traversed , It must not meet the requirements . Improved version :

#  Improved version of violent solution 
@cout_time
def two_sum_02(nums,target):
    for i in range(len(nums)):
        for j in range(i+1,len(nums)):
            if nums[i] + nums[j] == target:
                return [i,j]
    return []


if __name__ == '__main__':
    nums = list(range(1000))
    target = 1990
    resIndex = two_sum_01(nums, target)
    print("res: {}".format(resIndex))
    print("=========================================")
    resIndex = two_sum_02(nums,target)
    print("res: {}".format(resIndex))

result :

You can see it , Speed has improved .

solution 3: Use list The correlation function of

The idea of solving the problem is num2 = target - num1, Just judge num2 Is it in nums in : The following two methods are mainly used :
num2 in nums, return True On behalf of there
nums.index(num2), lookup num2 The index of

@cout_time
def two_sum_03(nums, target):
    j = -1
    for i in range(len(nums)):
        num1 = nums[i]
        num2 = target - num1
        if num2 in nums:
            if ((nums.count(num2) == 1) & (num2 == num1)):
                continue
            else:
                j = nums.index(num2, i + 1)
                break

    if j > 0:
        return [i, j]
    else:
        return []
if __name__ == '__main__':
    nums = list(range(1000))
    target = 1990
    resIndex = two_sum_01(nums, target)
    print("res: {}".format(resIndex))
    print("=========================================")
    resIndex = two_sum_02(nums, target)
    print("res: {}".format(resIndex))
    print("=========================================")
    resIndex = two_sum_03(nums, target)
    print("res: {}".format(resIndex))

result :

Time is shortened again

Method 4: Method 3 Improved version ,num2 The search does not need to start every time nums Look it up , Just from num1 Search before or after the position . For convenience index, Here choose from num1 Find before location .

@cout_time
def two_sum_04(nums, target):
    index1 = -1
    index2 = -1
    for i in range(1, len(nums)):
        index1 = i
        num1 = nums[i]
        num2 = target - num1
        tempNums = nums[:i]
        if num2 in tempNums:
            index2 = tempNums.index(num2)
            break
    if index2 >= 0:
        return [index2, index1]


if __name__ == '__main__':
    nums = list(range(1000))
    target = 1990
    resIndex = two_sum_01(nums, target)
    print("res: {}".format(resIndex))
    print("=========================================")
    resIndex = two_sum_02(nums, target)
    print("res: {}".format(resIndex))
    print("=========================================")
    resIndex = two_sum_03(nums, target)
    print("res: {}".format(resIndex))
    print("=========================================")
    resIndex = two_sum_04(nums, target)
    print("res: {}".format(resIndex))

result :

The time is shortened

solution 5: The dictionary simulates hashing . Simulate the process of hash query through dictionary . Store the data in a dictionary according to the index and value

One thing to note here , hold nums As the key of the dictionary ,nums Index as value . Here's the problem , Is how to deal with the same value ! Let's take an example :

The same value will be overwritten , That is, save the index of the last repeating element , So even if there are repeating elements , The index of the last repeating element is obtained during traversal , The traversal is from front to back , So if the target element to be found is two identical elements , It is also a good way to find the target solution .

@cout_time
def two_sum_05(nums, target):
    #  Save it in the dictionary first 
    hashDict = {
    }
    for index, num in enumerate(nums):
        hashDict[num] = index

    for i in range(len(nums)):
        index1 = i
        index2 = hashDict.get(target - nums[i])
        if index2 is not None and index1 != index2:
            return [index1,index2]


if __name__ == '__main__':
    nums = list(range(10000))
    target = 12222
    resIndex = two_sum_01(nums, target)
    print("res: {}".format(resIndex))
    print("=========================================")
    resIndex = two_sum_02(nums, target)
    print("res: {}".format(resIndex))
    print("=========================================")
    resIndex = two_sum_03(nums, target)
    print("res: {}".format(resIndex))
    print("=========================================")
    resIndex = two_sum_04(nums, target)
    print("res: {}".format(resIndex))
    print("=========================================")
    resIndex = two_sum_05(nums,target)
    print("res: {}".format(resIndex))

result : Let's enlarge the data , The difference can be clearly seen :

Method 6: above hashDict Optimized version

Unwanted num2 Throughout dict To find the . Can be in num1 Previous dict Search for , Therefore, only one cycle is needed to solve .

@cout_time
def two_sum_06(nums, target):
    hashDict = {
    }
    for index, num in enumerate(nums):
        if hashDict.get(target - num) is not None:
            return [hashDict.get(target - num),index]
        hashDict[num] = index



if __name__ == '__main__':
    nums = list(range(10000))
    target = 12222
    resIndex = two_sum_01(nums, target)
    print("res: {}".format(resIndex))
    print("=========================================")
    resIndex = two_sum_02(nums, target)
    print("res: {}".format(resIndex))
    print("=========================================")
    resIndex = two_sum_03(nums, target)
    print("res: {}".format(resIndex))
    print("=========================================")
    resIndex = two_sum_04(nums, target)
    print("res: {}".format(resIndex))
    print("=========================================")
    resIndex = two_sum_05(nums, target)
    print("res: {}".format(resIndex))
    print("=========================================")
    resIndex = two_sum_06(nums,target)
    print("res: {}".format(resIndex))

result : And the above method , The effect of improvement is not very obvious .

2. Addition of two numbers

① subject

Here are two non empty linked lists , Represents two nonnegative integers . Each of them is stored in reverse order , And each node can only store one digit .
Please add up the two numbers , And returns a linked list representing sum in the same form . You can assume that in addition to the numbers 0 outside , Neither of these numbers 0 start .

② Example

 Input ：l1 = [2,4,3], l2 = [5,6,4]
 Output ：[7,0,8]
 explain ：342 + 465 = 807.

Example 2:

 Input ：l1 = [0], l2 = [0]
 Output ：[0]

Example 3:

 Input ：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
 Output ：[8,9,9,9,0,0,0,1]

④ answer

solution 1: First understand the topic , First, the order from the head to the tail of the linked list in the title , Just a bit -> Order to higher bits . Therefore, the current bit of the obtained result only needs to be considered after adding , Then add the carry of the previous node , Yes 10 Modeling is the end result , Then the carry of the new next node carry Is the current node's (val1+val2+carry) // 10

Algorithm steps :

First the l1 and l2 The value of the head node is added up and assigned to the head node of the new linked list
Traversing two linked lists , As long as there is a linked list that has not been traversed , Just continue to traverse , When a linked list ends , Assign its value to 0
Each iteration generates a current node cur The next node of , The value is the sum of the nodes corresponding to the linked list plus the current node cur The resulting carry .
Update the current node after carry cur Value
At the end of the cycle , Because the last node may also generate carry , So if the value of the last node is two digits , To add a new node , The assignment is carry
Return to the header node

Code implementation :

def add_two_numbers(l1, l2):
    head = ListNode(l1.val + l2.val)
    cur = head  #  Head node 
    while l1.next or l2.next:
        l1 = l1.next if l1.next else ListNode(0)  #  The value of the next node 
        l2 = l2.next if l2.next else ListNode(0)  #  The value of the next node 
        cur.next = ListNode(l1.val + l2.val + cur.val // 10)
        cur.val = cur.val % 10
        cur = cur.next  #  The current node points to the next node 

    #  Judge the last node , If it's double digits , Just one more 
    if cur.val >= 10:
        cur.next = ListNode(cur.val // 10)
        cur.val = cur.val % 10
    return head

solution 2: Also traverse the linked list , Just carry and linked list L1 and L2, Is to accumulate separately , Existence accumulates , It doesn't exist .

def add_two_numbers_01(Ln1, Ln2):
    """  Add two numbers , Linked list  :param Ln1: :param Ln2: :return: """
    #  First create a virtual node , And create a current The pointer , Point to this node 
    current = dummy = ListNode()
    #  initialization carry The value added to the corresponding nodes of two linked lists 
    carry, value = 0, 0

    while carry or Ln1 or Ln2:
        value = carry
        if Ln1:
            Ln1, value = Ln1.next, Ln1.val + value

        if Ln2:
            Ln2, value = Ln2.next, Ln2.val + value

        carry, value = divmod(value, 10)
        current.next = ListNode(value)
        current = current.next

    return dummy.next

3. The longest substring of an unrepeated string

① subject

Given a string s, Please find out that there are no duplicate characters in it Longest substrings The length of .

② Example

Example 1:

 Input : s = "abcabcbb"
 Output : 3 
 explain :  Because the longest substring without repeating characters is  "abc", So its length is  3.

Example 2:

 Input : s = "bbbbb"
 Output : 1
 explain :  Because the longest substring without repeating characters is  "b", So its length is  1.

Example 3:

 Input : s = "pwwkew"
 Output : 3
 explain :  Because the longest substring without repeating characters is  "wke", So its length is  3.
      Please note that , Your answer must be   Substring   The length of ,"pwke"  Is a subsequence , Not substring .

③ answer

solution 1: The most intuitive feeling is to traverse , Then find all the substrings , Then record the largest substring .

The problem solving steps :

Double traversal , The first level traversal starts from the first bit
The second layer traverses , Start at the beginning of the first layer traversal , Then find out if there is a repeating element , If there are duplicate elements, exit the traversal .
Finally, according to the length of the substring , Record the maximum . This is implemented according to the substring slice , It is realized by judging whether the slice of the substring has repeating elements .

@cout_time
def length_of_longest_substring_01(s):
    """  Get the length of the longest non repeating substring  :param s: :return: """
    sLen = len(s)
    if sLen == 1:
        return 1
    maxLen = 0
    for i in range(sLen):
        for j in range(i, sLen):
            subStr = s[i:j+1]
            #  If it's the last one , Just go back to 
            if j == sLen - 1:
                if len(subStr) > maxLen:
                    maxLen = len(subStr)
                break
            if s[j+1] in subStr:
                if len(subStr) > maxLen:
                    maxLen = len(subStr)
                break  #  Exit inner loop , And record that length 
    return maxLen


if __name__ == '__main__':
    s = "abcabcbbabcedfeasdf"*10000
    res = length_of_longest_substring_01(s)
    print("res: {}".format(res))

result :

solution 2: The sliding window .

Explain the sliding window :

Sliding window is an idea based on double pointer , A window is formed between the elements pointed to by the two pointers .

The core idea :

Hold a window , It can be understood as a queue , At the beginning, the boundary of the window is left,right, At this point they are coincident , So the size of the window is 0
First expand the right boundary , Until the next element appears in [left,right) Within the interval , Just delete the elements of the window from the left , Until there are no repeating elements
Then expand the right boundary , Duplicate element occurred , Then delete the left boundary , Until the end

@cout_time
def length_of_longest_substring_02(s):
    if not s:
        return 0
    left = 0
    subStr = set()
    n = len(s)
    maxLen = 0
    curLen = 0
    for i in range(n):
        curLen += 1
        while s[i] in subStr:
            subStr.remove(s[left])
            left += 1
            curLen -= 1
        if curLen > maxLen:
            maxLen = curLen
        subStr.add(s[i])
    return maxLen

if __name__ == '__main__':
    s = "abcabcbbabcedfeasdf" * 50000
    res = length_of_longest_substring_01(s)
    print("res: {}".format(res))

    print("========================================")
    res = length_of_longest_substring_02(s)
    print("res: {}".format(res))

result :

The sliding window obviously increases its speed !

4. Find the median of two positive arrays

① subject

Given two sizes, they are m and n Positive order of ( From small to large ) Array nums1 and nums2. Please find and return the median of these two positive arrays . The time complexity of the algorithm should be O(log(m+n))

② Example

Example 1:

 Input ：nums1 = [1,3], nums2 = [2]
 Output ：2.00000
 explain ： Merge array  = [1,2,3] , Median  2

Example 2:

 Input ：nums1 = [1,2], nums2 = [3,4]
 Output ：2.50000
 explain ： Merge array  = [1,2,3,4] , Median  (2 + 3) / 2 = 2.5

③ answer

solution 1: Violence solution

Put two arrays , Merge
Sort , Take the median .

It should not meet the requirements , But learning , I also wrote about . It's used here list Some properties of , Like mergers , Sorting for example ;

@cout_time
def find_median_sorted_arrays_01(nums1, nums2):
    nums1.extend(nums2)
    nums1.sort()
    #  Judge whether the number is odd or even 
    if len(nums1) % 2 == 0:
        midIndex = int(len(nums1) / 2) - 1
        medianVal = (nums1[midIndex] + nums1[midIndex + 1]) / 2
    else:
        midIndex = int(len(nums1) / 2)
        medianVal = nums1[midIndex]
    return medianVal


if __name__ == '__main__':
    num1 = list(range(10000))
    num2 = list(range(10000,100000))

    res = find_median_sorted_arrays_01(num1, num2)
    print("res: {}".format(res))

solution 2: Loop traversal , But there is no need to merge the two lists .

Since the length of the two arrays is known , Therefore, the subscript positions of the two arrays corresponding to the median are also known . But here we have to distinguish between even numbers and odd numbers .

If it's odd , such as [1,2,3], [4,5], len = 5. The subscript position of the median is len / 2, So we have to traverse len/2 Time .
If it's even , such as [1,2,3],[4,5,6], len = 6. The subscript position of the median is len / 2 ,len / 2 - 1, So the number of iterations is also len/2 Time .

We maintain a pointer , Then follow certain rules to traverse len / 2 Time , The final structure is the median , Just according to len To judge parity and finally find the median .

Then the array traversal , Limiting conditions .
use aStart and bStart Respectively indicate that the current point is A Array and B The position of the array . If aStart It's not the end yet, and at this time A The number of the position of is less than B An array of positions , It took so long to move back .

If B The array has no numbers now , Keep taking numbers B[bStart] Will cross the border , So judge bStart Is it greater than the length of the array .

@cout_time
def find_median_sorted_arrays_02(nums1,nums2):
    m = len(nums1)
    n = len(nums2)
    lens = m +n
    aStart,bStart = 0,0
    left = right = -1,-1
    for i in range(int(lens / 2) + 1):
        left = right
        if aStart < m and (bStart >= n or nums1[aStart] < nums2[bStart]):
            right = nums1[aStart]
            aStart += 1
        else:
            right = nums2[bStart]
            bStart += 1

    if (lens & 1) == 0:
        return (left + right) / 2.0
    else:
        return right





if __name__ == '__main__':
    num1 = list(range(10000))
    num2 = list(range(10000,100000))

    res = find_median_sorted_arrays_01(num1, num2)
    print("res: {}".format(res))

    res = find_median_sorted_arrays_02(num1,num2)
    print("res: {}".format(res))

result :

solution 3: Dichotomy search

Ideas :

notice O(log(m+n)) And an ordered sequence of numbers , It's not hard to think of using Two points search To solve this problem .

First step : Exchange order

To reduce thinking , Let us first assume that the length of a sequence is not greater than the second .
If big , Just exchange . We assume that len(nums1) <= len(nums2)
If you don't exchange at first nums1 and nums2,mid2 = half_len - mid1 It could be negative .

Record the length of the two sequences

len1,len2 = len(nums1),len(nums2)

Record the information of binary search

How to search in two ?
Suppose the two sequences are merged in sequence , So the middle point is (len1 + len2 + 1) // 2
Suppose the median of this ideal is x
Consider the general situation , The first sequence has a number , The left side is less than x, On the right are greater than x.
The same is true for the second sequence
The positions of these two numbers in their respective sequences are called mid1 and mid2.
We first perform a binary search on the first sequence
Record the left border , The right boundary is the left and right boundary of the first sequence
The middle of the search is the middle point of the left and right boundaries .
about mid2, That is (len1 + len2 + 1) // 2 subtract mid1

Update the conditions for binary search :

Think like this , Ideally , Two sequences of mid1 and mid2 It should be the same .
Now mid1 Left and right mid2 The numbers on the left should be greater than mid1 and mid2 The number on the right is small .
So it's certain that , If mid2 The number ratio on the left mid1 The numbers on the right are all large , So the first sequence mid1 Too close to the left .
You can think so , If mid2 The number ratio on the left mid1 The ones on the right should be large , It's better to choose a smaller number for the second sequence and a larger number for the first sequence , So the two numbers will be closer .
To turn the middle of the first sequence to the right , That is, the update of binary search left
Conversely, update right, Remember mid1 Don't cross the upper limit !

while left < right:
    if mid1 < len1 and nums2[mid2-1] > nums1[mid1]:
        left = mid1 + 1
    else:
        right = mid1
    mid1 = (left + right) // 2
    mid2 = half_len - mid1

Return to the situation judgment :

Completed such binary search , We find the median of the first sequence and the median of the second sequence
Which one are we going to return ? Or return half of them ?
If the sum of the lengths of two sequences is odd , Then there is a unique middle number
If it's even , Is the average of the two median values .
Let's imagine that two sequences merge and sort , Then there is the median divided into two parts
We need a maximum on the left and a minimum on the right
How to find the maximum value on the left ?
Usually , We have found the second way mid1 and mid2, Compare the two numbers
The small one is the minimum value on the right .
contrast mid1 and mid2 The number on the left , The big one is the maximum value on the left .
Why is this logic ? Why are the two numbers on the left the maximum on the left , And itself is the minimum value on the right ? Why is it not that they are both high and low ?
This is because we started from 0 To (m + n) // 2 A total of (m + n) // 2 + 1 Number （ Because the subscript 0 It's also a number ）, This is more than half . And after subtracting these two median values , The rest is exactly half the quantity . This is the left half . So we're looking for mid It should be divided into the right part . Here you can find several more test samples to test several times .
by the way , There are also some special circumstances that have not been considered , For example, when the first line is very small , So left big is two lines mid2 To the left , And the right small is two lines mid2.
If the total is odd , Then the output is left large , If it's even , Output the average of left large and right small .

@cout_time
def find_median_sorted_arrays_03(nums1, nums2):
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1
    len1, len2 = len(nums1), len(nums2)

    left, right, half_len = 0, len1, (len1 + len2 + 1) // 2
    mid1 = (left + right) // 2
    mid2 = half_len - mid1

    while left < right:
        if mid1 < len1 and nums2[mid2 - 1] > nums1[mid1]:
            left = mid1 + 1
        else:
            right = mid1
        mid1 = (left + right) // 2
        mid2 = half_len - mid1

    if mid1 == 0:
        max_of_left = nums2[mid2 - 1]
    elif mid2 == 0:
        max_of_left = nums1[mid1 - 1]
    else:
        max_of_left = max(nums1[mid1 - 1], nums2[mid2 - 1])

    if (len1 + len2) % 2 == 1:
        return max_of_left

    if mid1 == len1:
        min_of_right = nums2[mid2]
    elif mid2 == len2:
        min_of_right = nums1[mid1]
    else:
        min_of_right = min(nums1[mid1], nums2[mid2])

    return (max_of_left + min_of_right) / 2


if __name__ == '__main__':
    num1 = list(range(10000))
    num2 = list(range(10000, 100000))

    res = find_median_sorted_arrays_01(num1, num2)
    print("res: {}".format(res))

    res = find_median_sorted_arrays_02(num1, num2)
    print("res: {}".format(res))

    res = find_median_sorted_arrays_03(num1, num2)
    print("res: {}".format(res))

result :

You can see that the speed is very fast , It's like the algorithm in front of the second kill .

5. Longest palindrome string

① subject

Give you a string s, find s The longest palindrome substring in .

② Example

Example 1:

 Input ：s = "babad"
 Output ："bab"
 explain ："aba"  It's the same answer .

Example 2:

 Input ：s = "cbbd"
 Output ："bb"

③ answer

First of all, popularize science , What is palindrome string ?

This string is symmetrical , Whether it's looking from front to back , Or from the back to the front , It's all the same .

solution 1: Violence solution , Traversing all strings , Then find the longest palindrome substring . It is a bit similar to the previous solution for finding substrings without repeated strings :

The first is to understand the palindrome substring , The length must be greater than 2, If the length is 1, Definitely not a palindrome string .
Judge the beginning of a character , Whether the position to the end of another character is a palindrome string , If it is , Just record the length , And the corresponding palindrome string .
Iterate through , And then update .

@cout_time
def longest_palindrome_01(s):
    """  The longest palindrome number solution 1 :param s: :return: """
    if len(s) <= 1:
        return s
    maxLen = 0
    sRes = ""
    for i in range(len(s) - 1):
        for j in range(i + 1, len(s) + 1):
            subs = s[i:j]
            if subs == subs[::-1]:
                if len(subs) > maxLen:
                    sRes = subs
                    maxLen = len(subs)
    return sRes if sRes != "" else sRes[0]

This algorithm is time-consuming , Failed to pass the test .

solution 2: You can start traversing from the longest substring , Then find the palindrome string and return , So you don't have to traverse all the substrings :

@cout_time
def longest_palindrome_02(s):
    length = len(s)
    if length < 2:
        return s
    for i in range(length, 0, -1):
        for j in range(length - i + 1):
            subStr = s[j:j + i]
            if subStr == subStr[::-1]:
                return subStr
    return ""

solution 3: Dynamic programming

Ideas and algorithms

For a substring , If it's a palindrome string , And the length is longer than 2, Then remove the last two letters , It is still a palindrome string . For example, for Strings abcba, If we already know bcb It's a palindrome string , The characters on both sides are the same , that abcba It must be a palindrome string .

According to this idea , We can solve this problem by dynamic programming . We use it P(i,j) Representation string s Of the i To j A string of letters ( The following is expressed as s[i:j]) Whether it is palindrome string :

The other cases here involve two possibilities :

s[i,j] Itself is not a palindrome string .
i > j, here s[i,j] Itself illegal .
Then we can write the state transition equation of dynamic programming :

in other words , Only s[i+1,j-1] Is a palindrome string and s Of the i Elements and number j When the elements are the same ,s[i:j] Is the palindrome string .

All the above discussion is based on the fact that the substring length is greater than 2 On the premise of , We also need to consider the boundary conditions in dynamic programming , That is, the length of the substring is 1 perhaps 2. For length is 1 The string of , It is obviously a palindrome string ; For length is 2 The string of , As long as its two letters are the same , It's just a palindrome string . So we can write the boundary conditions of dynamic programming :

According to this idea , We can complete dynamic planning , The final answer is all P(i,j) = true in j - i + 1( That is, the length of the substring ) The maximum of . Be careful : In the state transition equation , We transfer from a shorter string to a longer string , Therefore, we must pay attention to the cyclic order of dynamic programming .

@cout_time
def longest_palindrome_03(s):
    length = len(s)
    if length < 2:
        return s
    maxLen = 1
    begin = 0
    # dp[i][j]  Express s[i..j] Is it a palindrome string 
    dp = [[False] * length for _ in range(length)]
    for i  in range(length):
        dp[i][i] = True

    #  Recurrence start 
    #  First enumerate the length of substring 
    for L in range(2,length+1):
        #  Enumerate the left boundary , The upper limit of the left boundary can be set loosely 
        for i in range(length):
            #  from L  and i  You can determine the right boundary , namely  j - i + 1 = L
            j = L + i -1
            #  If the right boundary is out of bounds , You can exit the current loop 
            if j >= length:
                break

            if s[i] != s[j]:
                dp[i][j] = False
            else:
                if j - i <3:
                    dp[i][j] = True
                else:
                    dp[i][j] = dp[i+1][j-1]

            #  as long as dp[i][L] == True establish , It means substring s[i...L] It's palindrome. , At this point, record the palindrome length and starting position 
            if dp[i][j] and j - i + 1 > maxLen:
                maxLen = j - i + 1
                begin = i
    return s[begin:begin+maxLen]

result :

The time of dynamic planning is faster :

solution 4: Center expansion algorithm

Ideas and algorithms :

Let's take a closer look at the state transition equation of the dynamic programming method :

Find the state transition chain :

You can find , The possibility of all States in transition is unique . in other words , We can start with each boundary case [ Expand ], You can also get the answers corresponding to all the States .

The boundary case is that the length of the substring is 1 perhaps 2 The situation of . We enumerate each boundary case , And continuously expand from the corresponding substring to both sides . If the letters on both sides are the same , We can continue to expand , For example, from P(i+1,j-1) Extended to P(i,j); If the letters on both sides are different , We can stop expanding , Because the substring after this can't be a palindrome string .

therefore , We found that , The substring corresponding to the boundary case is actually the result of our extended palindrome string ( Palindrome Center ). The essence of this method is : We enumerate all palindrome centers and try to extend , Until it cannot be extended , At this time, the length of the palindrome string is this ( Palindrome Center ) The longest palindrome length under . We find the maximum for all lengths , You can get the final answer .

def expand_around_center(s, left, right):
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    return left + 1, right - 1


@cout_time
def longest_palindrome_04(s):
    start, end = 0, 0
    for i in range(len(s)):
        left1, right1 = expand_around_center(s, i, i)
        left2, right2 = expand_around_center(s, i, i + 1)
        if right1 - left1 > end - start:
            start, end = left1, right1

        if right2 - left2 > end - start:
            start, end = left2, right2
    return s[start:end + 1]