【python学习记录5】Longest Palindromic Substring

问题描述

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

详细问题

代码实现

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        lens = len(s)
        if lens < 2 :
            return s
        maxlen = 0
        maxl = 0
        maxr = 0
        i = 0
        while i < lens :
            if (lens-i) < maxlen//2 :
                break
            j = i
            k = i
            while (k<lens-1) and (s[k+1]==s[j]) : #寻找最大相同字符的子串作为核
                k = k+1
            i = k+1 #跳过同一核中的其他i
            while (j>0) and (k<lens-1) and (s[j-1]==s[k+1]) :
                j = j-1
                k = k+1
            if k-j+1 > maxlen :
                maxlen = k-j+1
                maxl = j
                maxr = k
        return s[maxl:maxr+1]

经验总结

• 寻找最大回文数，先寻找最大相同字符的子串作为核，从核开始扩展
• 要熟悉 {while（条件）自增} 的结构，寻找满足条件的最大情况