LeetCode讲解篇之5. 最长回文子串
文章目录
- 题目描述
- 题解思路
- 题解代码
题目描述
题目链接
题解思路
从中心点先寻找和中心点相等的左右端点，在基于左右端点进行往外扩散，直至左右端点不相等或者越界，然后左右端点这个范围内就是我们找寻的回文串，我们遍历中心点，就能执行上述流程就能查询所有的回文串，我们只需要取其中的最长的回文子串即可
题解代码
func longestPalindrome(s string) string {
n := len(s)
// 结果
ans := ""
// 遍历中心节点
for i := 0; i < n; i++ {
// 找寻不等于中心节点的左右端点
l, r := i, i
for l > 0 && s[l - 1] == s[i] {
l--
}
for r < n - 1 && s[r + 1] == s[i] {
r++
}
// 左右边界进行扩散，直至左右端点不相等或者越界
offset := 1
for l - offset >= 0 && r + offset < n && s[l - offset] == s[r + offset] {
offset++
}
// 刷新最长回文子串
tmp := s[l - offset + 1:r + offset]
if len(tmp) > len(ans) {
ans = tmp
}
// 减枝，减少重复回文子串的计算
i = r
}
return ans
}