题解 | #密码截取#
密码截取
https://www.nowcoder.com/practice/3cd4621963e8454594f00199f4536bb1
这道题可以用动态规划,定义dp为表示两端索引为i,j的字符段是否回文串的二维数组,
可以参考********最长回文子串,但是这种解法空间复杂度为O(n2),占用内存过多,
我使用的是双指针,空间复杂度0(1),时间复杂度O(n2)。
思路就是遍历每个字符,由这个字符向两边扩展,两端字符相同继续扩展,同时更新最大长度,
否则退出循环,因为子串可能是奇数可能是偶数,所以需要两种情况分别遍历
code = input() n = len(code) if n<=1: print(code) max_lo = 1 max_le = 0 for i in range(1,n-1): left,right = i-1,i+1 while 0<=left<right<n and code[left]==code[right]: max_lo = max(max_lo,right-left+1) left-=1 right+=1 for i in range(n-1): left,right = i,i+1 while 0<=left<right<n and code[left]==code[right]: max_le = max(max_le,right-left+1) left-=1 right+=1 print(max(max_lo,max_le))