@@-M-5. Longest Palindromic Substring

@@代表不是特别难, 但是值得反复练手的题目, 通常包括一些细节问题, 以及代码结构的练习

Loading...LeetCode

# 这题思路其实巨简单.. 就是写代码要写的简洁明了, 适合反复练习

# 0 O(n^2), O(n)思路很简单, 就是从左往右在把一个间隙和数字当做当前可能额palindrome开始往两边
# 扩展, 如果一直符合palindrome就一直扩展直到不满足为止, 然后记录下这个palindrome, 然后再和之前
# 暂存的最长的palindrome比大小, 保留大的那个

# 另外这个方法的空间复杂度可以优化到O(1), 就是不要直接传str和比较len(str), 全程用传下标即可, 
# 比也是拿下标的right-left就好了, 最终输出res即可.(输出不考虑到空间复杂度里面, 当然如果输出也算空间
# 复杂度的话, 那这样最终还是O(n), 因为res无论如何都要存一个O(n)的str的)
class Solution:
    def longestPalindrome(self, s: str) -> str:
        def check_palindrome(left, right):
            # 这个while很精髓
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
                    
            return s[left+1:right]
            
        if not s:
            return ''
        res = s[0]
        
        for i in range(1, len(s)):
            odd = check_palindrome(i, i)    
            even = check_palindrome(i-1, i)
            # 注意这里max的用法
            res = max(odd, even, res, key = len)
            
        return res