题解 | #最长回文子串#

package main

import (
    "fmt"
)

func main() {
    // 获取输入并初始化结果
    var input string
    fmt.Scan(&input)
    res:=""
    // 现学的动态规划
    dp := make([][]bool, len(input))
    // 初始化这个二维数组
    for i:=0;i<len(input);i++{
        dp[i]=make([]bool, len(input))
    }
    // 反向遍历顺带进行判断
    // 外围的反向遍历是因为正常遍历的话dp[i+1][j-1]这个值拿不到，可以自己画个图验证一下
    for i:=len(input)-1;i>=0;i--{
        // 内部遍历
        for j:=i;j<len(input);j++{
            if i==j{
                // 相等的话就是意味在同一个位置上
                dp[i][j]=true
            }else if j-i==1{
                // 这边是长度为2的子字符，需要判断一下input的i和j位置上的两个字符是否一样
                dp[i][j]=input[i]==input[j]
            }else{
                // 大于2的字符串除了判断两段，还要判断去除两段的部分是否回文
                dp[i][j]=(input[i]==input[j])&&dp[i+1][j-1]
            }
            // 判断一下最大长度
            // 这边的j-i+1是要处理ji重叠的情况，彼时长度至少是1
            if dp[i][j]&&(j-i+1)>len(res){
                // 截取i到j，golang字符串截取最右边不包括，所以要加一
                res=input[i:j+1]
            }
        }
    }
    fmt.Println(len(res))

}