Question 5 Longest Palindromic Substring

The description of the question in the following link

https://leetcode.com/problems/longest-palindromic-substring/submissions/

My Code:

Explanation:

As we are looking for the substring, the idea is straightforward: writing a function that checks all the substring with possible length, from 1 to the length of whole string. The only thing that we need to be very careful is about the index of the substring. I have made several mistakes, and I want to summarize some useful situations here.

Assume z is a string, with length k;

1. z[j] : Take the j+1 th element in the string. (j < k)
2. z[j:j+i]: Take the substring from j to j+i-1
3. z[-j]: Take the jth last element of the string (starting from -1)
4. z[::-1]: Reverse the string
5. z[i:i] : Gives nothing (null)

Hence the first loop of the code initialize all the possible length, from 1 to total length.

The second loop gives all the possible starting checking point for each i given by the first loop indicator. Hence we may check all the possible substring and determine the longest palindromic substring.

P.S. When I am writing this review, I have an idea that may improve the speed of this code. 1. We may start from the longest substring to shortest. Whenever we find the longest one we do not need to continue the search.

2. Code by another submitter ；

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def check(l, r):
            while 0 <= l <= r < len(s) and s[l] == s[r]:
                l -= 1
                r += 1
            return s[l + 1:r]
        pals = [check(i, i) for i in range(len(s))] + [check(i, i + 1) for i in range(len(s) - 1) if s[i] == s[i + 1]]
        return sorted(pals, key = len)[-1] if pals else ''

The idea of this code is to start from each element in the string and start the comparison between left and right expansion. The second last line first summand is to check when the centre of the palindromic substring is a single letter and the second summand is to check when the centre of the palindromic substring is two same letters. And the sum is a list with all the palindromic string.  The last line is to do the sort based on the length of the strings and return the last one which has the longest length.