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
}

原文地址：https://blog.csdn.net/qq_67733273/article/details/142613608

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！