最长回文子串

提供一个新思路,通过回文字符串的特性,正反读取都相同,可以将字符串逆转后,求取最长公共子串,但可能会出现其他部分重置与另一部分相同,所以需要对比找到最长公共子串的索引与原索引相加是否为字符串长度-1,即 i+j-tmp[j+1]+1== len(A)-1,如果相等,则更新最长回文子串.

更新: 此处应该判断的是 i - 最长公共子串长度 + 1 = 当前与i匹配的字符原索引 (L - 1 -j)

func getLongestPalindrome( A string ,  n int ) int {
    // write code here
    if len(A) == 1{
        return 1
    }
    B := resever(A)
    res := make([]int,len(A)+1)
    max := 0
    for i:=0;i<len(a);i++{ tmp :="make([]int,len(A)+1)" for j:="0;j<len(B);j++{" if b[j]="=" a[i]{ tmp[j+1]> max &amp;&amp; i+j-tmp[j+1]+1== len(A)-1{
                    max = tmp[j+1]
//                     fmt.Println(tmp)
                }
            }else{
                tmp[j+1] = 0
            }
        }
        res = tmp
    }
    return max
}

func resever(A string)string{
    tmp := []byte(A)
    for i,j:=0,len(A)-1;i</len(a);i++{>
全部评论
谢谢楼主,我一开始也是这个思路,但是我忽略了“但可能会出现其他部分重置与另一部分相同”的情况,结果只通过了95%的例子,感谢楼主的提醒,我加上这个条件后就通过了
1 回复 分享
发布于 2021-08-14 11:34
没有太明白忽略的这种情况,能举例子说明一下吗?
点赞 回复 分享
发布于 2021-08-29 13:38
解决了我的疑惑
点赞 回复 分享
发布于 2022-01-02 15:36

相关推荐

牛客154160166号:9月底还给我发短信,好奇怪,我24届的
点赞 评论 收藏
分享
与火:这不接? 留子的钱不挣白不挣
点赞 评论 收藏
分享
13 收藏 评论
分享
牛客网
牛客企业服务