5. 最长回文子串

一、5. 最长回文子串

参考了windliang的详细通俗的思路分析，多解法

1.1、题目描述

1.2、题解 1.2.1、暴力法（超时）

# 时间复杂度：两层 for 循环O(n²)，for 循环里边判断是否为回文 O(n)，所以时间复杂度为 O(n³)。

# 空间复杂度：O(1)，常数个变量。
 
class Solution:
    def longestPalindrome(self, s: str) -> str:
        print(self.isPalindromic("a"))
        n = len(s)
        maxC = 0

        ans = ""
        for i in range(n):
            for j in range(i+1, n+1):
                t = s[i:j]
                if self.isPalindromic(t) and len(t) > maxC:
                    maxC = len(t)
                    ans = t
        return ans    

    # 判断回文串
    def isPalindromic(self, s: str) -> bool:
        for i in range(len(s)//2):
            if s[i] != s[len(s)-i-1]:
                return False
        return True

1.2.2、最长公共子串

根据回文串的定义，正着和反着读一样，那我们是不是把原来的字符串倒置了，然后找最长的公共子串就可以了。例如 S = “caba” ，S = “abac”，最长公共子串是 “aba”，所以原字符串的最长回文串就是 “aba”。

1.2.2.1、寻找公共子串

class Solution:
    def longestPalindrome(self, s: str) -> str:
        word1 = s
        word2 = s[::-1]

        length= len(word1)
        # dp[j] 每次只需要前一行的数据
        dp = [[0]*(length) for _ in range(length)] 
        maxLen = 0
        endIdx = 0
        for i in range(length):
            for j in range(length):
                if word1[i] == word2[j]:
                    if i == 0 or j == 0:
                        dp[i][j] = 1
                    else:
                        dp[i][j] = dp[i-1][j-1] + 1

                if dp[i][j] > maxLen:
                	maxLen = dp[i][j]
                    endIdx= i
            
        return word1[endIdx-maxLen+1: endIdx+1]

1.2.2.2、剔除不是回文串的公共子串

class Solution:
    def longestPalindrome(self, s: str) -> str:
        word1 = s
        word2 = s[::-1]

        length= len(word1)
        # dp[j] 每次只需要前一行的数据
        dp = [[0]*(length) for _ in range(length)] 
        maxLen = 0
        endIdx = 0
        for i in range(length):
            for j in range(length):
                if word1[i] == word2[j]:
                    if i == 0 or j == 0:
                        dp[i][j] = 1
                    else:
                        dp[i][j] = dp[i-1][j-1] + 1
				
                if dp[i][j] > maxLen:
                	# 剔除不是回文串的公共子串
                    beforeRev = length - 1 - j
                    if beforeRev + dp[i][j] - 1 == i:
                        maxLen = dp[i][j]
                        endIdx= i
            
        return word1[endIdx-maxLen+1: endIdx+1]

1.2.2.3、优化空间复杂度

class Solution:
    def longestPalindrome(self, s: str) -> str:
        word1 = s
        word2 = s[::-1]

        length= len(word1)
        # dp[j] 每次只需要前一行的数据
        dp = [0]*(length)
        maxLen = 0
        endIdx = 0
        for i in range(length):
            # 注意此处
            for j in range(length-1, -1, -1):
                if word1[i] == word2[j]:
                    if i == 0 or j == 0:
                        dp[j] = 1
                    else:
                        dp[j] = dp[j-1] + 1
                else:
                    dp[j] = 0

                if dp[j] > maxLen:
                    beforeRev = length - 1 - j
                    if beforeRev + dp[j] - 1 == i:
                        maxLen = dp[j]
                        endIdx= i
            
        return word1[endIdx-maxLen+1: endIdx+1]
        

1.2.3、动态规划

1.2.3.1、二维dp

class Solution:
    def longestPalindrome(self, s: str) -> str:
        length= len(s)

        dp = [[0]*(length) for _ in range(length)]
        maxLen = 0
        maxs = ''
        for l in range(1, length+1): # 子串的长度
            for start in range(length): # 子串开始的位置
                end = l + start -1
                if end >= length:   # 越界
                    break;
                
                # 长度为1、2需要单独考虑
                # P(i,j)=(P(i+1,j−1)&&S[i]==S[j])
                dp[start][end] = (l==1 or l==2 or dp[start+1][end-1]) and s[start] == s[end]
                if dp[start][end] and l > maxLen:
                    maxs = s[start: end+1]
        return maxs
        

1.2.3.2、递推公式中我们可以看到，我们首先知道了 i+1 才会知道 i，所以我们只需要倒着遍历就行了。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        length= len(s)
        dp = [[False]*(length) for _ in range(length)]
        maxs = ''

        for i in range(length-1, -1, -1): 
            for j in range(i, length):
                # P(i,j)=(P(i+1,j−1)&&S[i]==S[j])
                dp[i][j] = (j-i len(maxs)) and dp[i][j]:
                    maxs = s[i: j+1]
        return maxs

1.2.3.3、一维dp

class Solution:
    def longestPalindrome(self, s: str) -> str:
        length= len(s)
        dp = [[False]*(length) for _ in range(length)]
        maxs = ''

        for i in range(length-1, -1, -1): 
            for j in range(length-1, i-1, -1):
                # P(i,j)=(P(i+1,j−1)&&S[i]==S[j])
                dp[j] = (j-i len(maxs)) and dp[j]:
                    maxs = s[i: j+1]
        return maxs

1.2.4、中心扩散法

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        start = end = 0
        for i in range(n):
            len1 = self.expandAroundCenter(s, i, i)
            len2 = self.expandAroundCenter(s, i, i+1)
            maxLen = max(len1, len2)
            if maxLen > end - start:
                start = i - (maxLen - 1) // 2
                end = i + maxLen // 2
        return s[start: end+1]
        
    def expandAroundCenter(self, s: str, l: int, r: int) -> int:
        L = l 
        R = r
        while L >= 0 and R  int:
        n = len(s)
        dp = [[False]*n for _ in range(n)]

        count = 0 
        # 单个字符都是回文串    
        for i in range(n):
            dp[i][i] = True
            for j in range(i+1):
                dp[i][j] = (i-j  int:
        n = len(s)
        count = 0
        for i in range(n):
            count += self.countPalindrome(s, i, i)
            count += self.countPalindrome(s, i, i+1)

        return count 
    
    def countPalindrome(self, s: str, left: int, right: int) -> int:
        n = len(s)
        count = 0
        while left >= 0 and right