容易超时的情况：全是相同字符串

不对的方法：O（n^3）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param A string字符串 
# @return int整型
#
class Solution:
    def getLongestPalindrome(self , A: str) -> int:
        max_length = 1
        for ind,i in enumerate(A):
            numbers_to_be_process = []
            for j in range(ind+1,len(A)):
                if A[ind]==A[j]:
                    numbers_to_be_process.append(j)
            
            for next_ind in numbers_to_be_process:
                left,right = ind,next_ind
                length = 0
                is_hw = True
                while left<=right:
                    if left==right:
                        length+=1
                        break
                    if A[left]!=A[right]:
                        is_hw = False
                        break
                    left+=1
                    right-=1
                    length +=2
                if is_hw:
                    max_length = max(max_length,length)
        return max_length

中心扩展法，时间复杂度O(n²)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def longest_palindrome(s: str) -> str:
	# 返回给定字符串的最长回文子串
    if not s:
        return ""
    
    start = 0
    end = 0

    for i in range(len(s)):
        len1 = expand_around_center(s, i, i)     # 奇数长度，此时左右指针都从中间开始
        len2 = expand_around_center(s, i, i + 1) # 偶数长度，从中间以及中间右边开始
        max_len = max(len1, len2)
        
        if max_len > end - start: # max_len表示本次的最长长度，end-start表示历史最长，节省了一个变量，
            start = i - (max_len - 1) // 2 # 中间减去一半
            end = i + max_len // 2

    return s[start:end + 1]

def expand_around_center(s: str, left: int, right: int) -> int:
	# 找到给定中心的最长回文子串
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    return right - left - 1

longest_palindrome('ababcb')
  • 为什么不用判断i+1超范围：expand_around_center(s, i, i + 1)该函数内部会自动处理
  • 为什么right - left - 1不也是right - left +1：循环退出时，left 和 right 已经扩展到不能继续为回文了，也就是指向非回文串第一个元素的前一个元素和最后元素的后一个元素，此时的 s[left+1 : right] 才是最后一个合法的回文子串

也可以直接返回首尾

动态规划，时间和空间复杂度都是O(n²)

设 dp[i][j] 表示子串 s[i..j] 是否为回文串的布尔数组

状态转移：

  • 若 s[i] == s[j] 且 dp[i+1][j-1] 为真，则 dp[i][j] 也为真。（也是中心扩展）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def longest_palindrome(s: str) -> str:
    n = len(s)
    if n < 2:
        return s

    dp = [[False] * n for _ in range(n)]
    start = 0
    max_len = 1

    for i in range(n):
        dp[i][i] = True  # 单个字符一定是回文串

    # j 是右边界，i 是左边界
    for j in range(1, n):
        for i in range(0, j):
            if s[i] != s[j]:
                dp[i][j] = False
            else:
                if j - i <= 2:
                    dp[i][j] = True  # "aa" or "aba" 情况
                else:
                    dp[i][j] = dp[i + 1][j - 1]
            
            if dp[i][j] and (j - i + 1 > max_len): # 如果是回文，且超过最大长度，记录长度和起始
                max_len = j - i + 1
                start = i

    return s[start:start + max_len]

长度为2和1的子串（如”aa”）必须特殊处理，

填充顺序：

在数组中表现为每个元素依赖于它左下的元素（行数+1，列数-1），因此左下元素必须被先计算，填充为i变j不变，行索引变，一列一列填充，这样其依赖元素必定被填充，因为在前一列，（行数不用管，因为前一列所有元素都被填充了）

蓝色表示依赖，红色表示填充顺序

由于j<i没有意义，即只填充i>=j的区域，2d数组右上角（主对角线右）