题解 | #最长回文子串#
最长回文子串
https://www.nowcoder.com/practice/b4525d1d84934cf280439aeecc36f4af
class Solution:
def huiwen(self, A, i, j):
while i >= 0 and j < len(A) and A[i] == A[j]:
i -= 1
j += 1
return j - i - 1
def getLongestPalindrome(self , A: str) -> int:
res = 1
for i in range(len(A) - 1):
res = max(res, max(self.huiwen(A, i, i), self.huiwen(A, i, i+1)))
return res
解题思路
- 遍历字符串，从当前位置向两侧进行扩展，找到最长的回文字符串，并与当前的回文字符串长度进行比较，取大值。
- 注意：在比较大小的时候，记得需要分奇数长度和偶数长度的情况判断是否是回文。
复杂度
- 时间复杂度为O（N^2）；
- 空间复杂度为O（1）。
查看7道真题和解析
投递兴业数金等公司10个岗位
