侧边栏壁纸
博主头像
hanlibaby博主等级

念念不忘,必有回响

  • 累计撰写 59 篇文章
  • 累计创建 92 个标签
  • 累计收到 21 条评论

LeetCode-5. 最长回文子串

hanlibaby
2021-11-28 / 0 评论 / 0 点赞 / 156 阅读 / 1,371 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2021-11-28,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题意

给你一个字符串 s,找到 s 中最长的回文子串。

示例1

输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。

示例2

输入:s = "cbbd"
输出:"bb"

解法

1、中心拓展

我们都知道回文串都是对称的,所以我们可以使用这个性质,每次选择一个中心,然后向两边拓展,判断两边字符是否相等即可。由于字符串长度存在奇数和偶数的区别,所以每次枚举中心的时候可以从一个字符作为中心进行拓展或者可以从两个字符的之间进行拓展。

leetcode5.PNG

leetcode52.PNG

参考代码:
1、Java
class Solution {
    private int getLen(char[] words, int l, int r) {
        if (l >= 0 && r < words.length && words[l] != words[r]) return 0;
        while (l >= 0 && r < words.length && words[l] == words[r]) {
            l -- ;
            r ++ ;
        }
        return r - l - 1;
    }
    
    public String longestPalindrome(String s) {
        char[] words = s.toCharArray();
        String res = "";
        int maxL = 0;
        for (int i = 0; i < words.length; i ++ ) {
            int len = getLen(words, i, i);
            if (len > maxL) {
                maxL = len;
                res = s.substring(i - len / 2, i + len / 2 + 1);
            }
            len = getLen(words, i - 1, i);
            if (len > maxL) {
                maxL = len;
                res = s.substring(i - len / 2, i + len / 2);
            }
        }
        return res;
    }
}
2、Go
func longestPalindrome(s string) string {
    res, maxL := "", 0
    for i := 0; i < len(s); i ++ {
        if wordLen := getLen(s, i, i); wordLen > maxL {
            maxL = wordLen
            res = string([]rune(s[i - wordLen / 2 : i + wordLen / 2 + 1]))
        }
        if wordLen := getLen(s, i - 1, i); wordLen > maxL {
            maxL = wordLen
            res = string([]rune(s[i - wordLen / 2 : i + wordLen / 2]))
        }
    }
    return res
}

func getLen(s string, l, r int) int {
    if l < 0 || r >= len(s) || s[l] != s[r] {
        return 0
    }
    for l >= 0 && r < len(s) && s[l] == s[r] {
        l --
        r ++
    }
    return r - l - 1
}
  • 时间复杂度:$O(n^2)$
  • 空间复杂度:$O(1)$
2、动态规划

动态规划的做法我在之前一篇文章中已经阐述过了,感兴趣的可以去看看。
链接:https://www.lwjppz.cn/2020/11/29/最长回文子串子序列问题总结

0

评论区