最长对称子串

最长对称子串-回文串-python

• • 思路
  • 解法

思路

1.创建二维数组
2.给二维数组赋初值
3.上三角形(斜对角线开始向左)与下三角形(斜对角线开始向右)分别计算
4.计算不同斜列连续的1的最长个数，即为最终最长回文串的长度

解法

动态规划(广义上的)-时间复杂度O(n^2)

s = input()
dp = []
for i in range(len(s)):  # 创建行列均为字符串长度的二维数组
    dp.append([0] * len(s))

for i in range(len(s)):  # 字符相同赋1，不同赋0
    for j in range(len(s)):
        if (s[i] == s[j]):
            dp[i][j] = 1
        else:
            dp[i][j] = 0

curr = 0  # 当前这轮(斜列)最长回文串长度
max = 0  # 全局最长回文串长度
for i in range(len(s)):  # 计算下三角形
    curr = 0
    flag = 0  # 标志：是否遇到了当前斜列的1
    fla = 1  # 标志：是否第一次遇到1
    for j, k in zip(range(i, len(s)), range(len(s) - 1, i - 1, -1)):
        if (dp[j][k] == 1):
            if (fla):
                tou = j  # 第一次遇到1，记录下来当前行数，后面计算curr的时候需要用
                fla = 0  # 遇到后置0
            flag = 1
            curr = j - tou + 1  # ！！注意赋值不要放在dp[i][j] == 0条件处，可能会遇到当前斜列以1结束的情况
        else:
            if (flag):  # 遇到了1后中途遇到了0，此连续回文串断裂，进行下一轮
                break
    if (curr > max):
        max = curr
    if (len(s) - i - 1 <= max):  # 如果之后的斜列全是1，但还是小于当前max，后面不用计算了，直接退出
        break

for i in range(len(s) - 1, -1, -1):  # 计算上三角形
    curr = 0
    flag = 0  # 标志：是否遇到了当前斜列的1
    fla = 1  # 标志：是否第一次遇到1
    for j, k in zip(range(i + 1), range(i, -1, -1)):
        if (dp[j][k] == 1):
            if (fla):
                tou = j  # 第一次遇到1，记录下来当前行数，后面计算curr的时候需要用
                fla = 0  # 遇到后置0
            flag = 1
            curr = j - tou + 1  # ！！注意赋值不要放在dp[i][j] == 0条件处，可能会遇到当前斜列以1结束的情况
        else:
            if (flag):  # 遇到了1后中途遇到了0，此连续回文串断裂，进行下一轮
                break
    if (curr > max):
        max = curr
    if (i+1 <= max):  # 如果之后的斜列全是1，但还是小于当前max，后面不用计算了，直接退出
        break

print(max)