题解 | #最长回文子串#

最长回文子串

http://www.nowcoder.com/practice/b4525d1d84934cf280439aeecc36f4af

我使用的是中心位置法,遍历去头去尾的字符串,若字符串左边右边相等,则两个指针定位左边右边,同时向外扩展直到不相等,则回文长度是right_point - left_point - 1;若字符串左边或者右边的某一位与该字符串相等,则指针定位这两个相等的字符,并同时向外扩展直到不相等,方法相同;算法时间复杂度N方,空间复杂度N,一个存放所有以该数为中心的回文长度

完整代码:

#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
# 
# @param A string字符串 
# @param n int整型 
# @return int整型
#
class Solution:
    def getLongestPalindrome(self , A: str, n: int) -> int:
        # write code here           
        dp = [1]*n
        if n ==1:
            return 1
        for i in range(1,n-1):
            if A[i-1] == A[i+1]:
                left_point ,right_point = i-1 , i+1
            elif A[i] == A[i-1]:
                left_point ,right_point = i-1 , i
            elif A[i+1] == A[i]:
                left_point ,right_point = i , i+1
            else:
                continue
            while left_point>=0 and right_point<n and A[left_point]==A[right_point]:
                left_point -= 1
                right_point += 1
            dp[i] = right_point - left_point - 1
        return max(dp)
全部评论
输入的是全一样的偶数个回文串时,输出的结果不对
1 回复 分享
发布于 2023-02-24 15:02 江苏
三个if条件不互斥,会有问题
1 回复 分享
发布于 2022-09-04 12:35 广东
原题没有输入n
点赞 回复 分享
发布于 2023-02-24 14:15 江苏
class Solution: def getLongestPalindrome(self, A: str) -> int: # write code here dp = 1 for i in range(0, len(A) - 1): if i>0 and A[i - 1] == A[i + 1]: left_point, right_point = i - 1, i + 1 while ( left_point >= 0 and right_point < len(A) and A[left_point] == A[right_point] ): left_point -= 1 right_point += 1 dp = max(dp, right_point - left_point - 1) if A[i + 1] == A[i]: left_point, right_point = i, i + 1 while ( left_point >= 0 and right_point < len(A) and A[left_point] == A[right_point] ): left_point -= 1 right_point += 1 dp = max(dp, right_point - left_point - 1) return dp
点赞 回复 分享
发布于 2022-09-24 14:12 上海
这对全一样的偶数个回文串不对,结果永远差一
点赞 回复 分享
发布于 2022-03-28 20:27
这个程序有2个用例过不了,不知道啥不对
点赞 回复 分享
发布于 2021-11-25 19:54
牛逼啊,有空帮忙指导下,哈哈
点赞 回复 分享
发布于 2021-11-17 10:15
大佬啊,get到了
点赞 回复 分享
发布于 2021-11-14 22:31
666,学习了👏👏
点赞 回复 分享
发布于 2021-11-14 15:33

相关推荐

不愿透露姓名的神秘牛友
07-04 14:23
steelhead:你回的有问题,让人感觉你就是来学习的
点赞 评论 收藏
分享
06-12 16:00
天津大学 Java
牛客30236098...:腾讯坏事做尽,终面挂是最破防的 上次被挂了后我连简历都不刷了
点赞 评论 收藏
分享
07-03 11:02
中山大学 C++
字节刚oc,但距离九月秋招很近了有两段互联网实习,非腾讯字节。不敢赌转正,现在在纠结去还是不去如果实习俩月离职会有什么后果吗
阿城我会做到的:不去后悔一辈子,能否转正取决于ld的态度,只要他不卡,答辩就是走流程,个人觉得可以冲一把
投递字节跳动等公司9个岗位
点赞 评论 收藏
分享
评论
12
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务