首页L2-008 最长对称子串python

L2-008 最长对称子串python

时间: 2023-11-12 18:59:57 浏览: 293

好的，关于 L2-008 最长对称子串，我可以给你一些思路和代码实现。首先，对于一个字符串，我们可以枚举每一个子串，然后判断该子串是否是回文串。但是这样的时间复杂度是 $O(n^3)$，显然会超时。因此，我们可以考虑优化。我们可以从中心向两边扩展，来判断回文串。具体来说，我们可以枚举每一个可能的中心位置，然后向两边扩展，直到不能扩展为止。这样的时间复杂度是 $O(n^2)$。具体实现可以参考下面的代码： ```python def longest_palindrome(s): n = len(s) max_len = 0 start = 0 for i in range(n): # 以 i 为中心的奇数长度回文串 l, r = i, i while l >= 0 and r < n and s[l] == s[r]: l -= 1 r += 1 if r - l - 1 > max_len: max_len = r - l - 1 start = l + 1 # 以 i 和 i+1 为中心的偶数长度回文串 l, r = i, i + 1 while l >= 0 and r < n and s[l] == s[r]: l -= 1 r += 1 if r - l - 1 > max_len: max_len = r - l - 1 start = l + 1 return s[start:start+max_len] ``` 这个函数的输入是一个字符串，输出是该字符串的最长回文子串。

阅读全文