5.最长回文子串

        给你一个字符串 s，找到 s 中最长的回文子串。

暴力解法：

• 枚举出s的所有子串的左下标值和其长度
• 判断字串是否是回文字串
• 截取子串（begin：begin+maxLen）

        第2，3步在算法中都类似，重要的是怎么简化第1步。

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        # 判断 回文子串 的算法
        def validPalindromic(s,left,right):
            while left < right:#逐个比较左右侧值是否相等
                if s[left]!=s[right]:
                    return False
                left+=1
                right-=1
            return True
 
        n = len(s)
        # 判断长度为1的字符串
        if n<2:
            return s
 
        maxLen = 1 
        begin = 0
        #枚举 所有长度严格大于1的字串，p[i...j]
        for i in range(n-1):#右边界前一位
            for j in range(1,n):#左边界后一位
                if (j-i+1 > maxLen and validPalindromic(s,i,j)):
                    maxLen = j-i+1  #子串长度递增
                    begin = i #左边界右移
        return s[begin:begin+maxLen]

         时间复杂度：，空间复杂度：

中心扩展算法：从中心考虑

• 将第1步简化为：枚举出所有中心字符串的中心位置和长度，需考虑子串长度为奇数、偶数的情况
• 判断：在左侧向左移动，右侧向右移动，且左右端值相等时，该子串为回文子串

class Solution(object):
    #中心扩散方法，判断是否为回文子串
    def expandAroundCenter(self, s,left,right):
        while left>=0 and right<len(s) and s[left] == s[right]:
            left-=1
            right+=1
        return left+1,right-1 #最后一步是条件不满足退出循环，所以下标值收缩一步
 
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        start,end = 0,0
        for i in range(len(s)):
            left1,right1 = self.expandAroundCenter(s,i,i)#偶数回文子串
            left2,right2 = self.expandAroundCenter(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]

         时间复杂度：，空间复杂度：

动态规划：

        回文子串状态转移的性质：在左右字符相同的情况下，中间字符串决定了子串是否属于回文子串。

        例如一个字符串m：m[0]==m[3]，且m[1:2]是回文序列，则m[1:3]是回文序列；m[2]==m[5]，且m[3:4]不是回文序列，则m[2:5]不是回文序列。

         对于字符串的子串P(i,j)，可以用如下表格记录子串是否是回文子串，根据表格可以看出，s[0:2]和s[1:3]都是回文子串。

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        n = len(s)
        if n<2:
            return s
 
        maxLen = 1
        begin = 0
        # 创建一个n*n的表格，初始化表格内容为False
        dp = [[False]*n for _ in range(n)]
        # 对角线元素都是回文子串
        for i in range(n):
            dp[i][i] = True
 
        # 枚举子串长度
        for L in range(2,n+1):     #n=6,n+1=7,L=2,3,4,5,6
            for i in range(n):
                # 右边界j
                j = L+i-1
                if j>=n:
                    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]
                if dp[i][j] and j-i+1>maxLen:
                    maxLen = j-i+1
                    begin = i
        return s[begin:begin+maxLen]

时间复杂度：，空间复杂度：

6.Z字形变换

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

矩阵填充

定义一个r*c的空矩阵，使用循环将s中的值以Z字型填入矩阵。输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：

• 首先根据行数确定Z字变换的周期t，再求出行数c，这里的c比实际占用行数多一行
• 遍历字符串s，当 s 下标 i 对周期 t 取余小于r-1时向下移动，否则向右上移动

class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        n = len(s)
        if numRows < n:return s
        t = numRows * 2 - 2
        c = (n + t - 1) // t * (numRows - 1)
        mat = [[''] * c for _ in range(numRows)] #创建空矩阵，c列，numRows行
        x, y = 0, 0
        for i, ch in enumerate(s):
            mat[x][y] = ch
            if i % t < numRows - 1:    #Z字移动的判断条件
                x += 1  # 向下移动
            else:
                x -= 1
                y += 1  # 向右上移动
        return ''.join(ch for row in mat for ch in row if ch) #取出非空字符