美文网首页
5.最长回文子串

5.最长回文子串

作者: 夜空中最亮的星_6c64 | 来源:发表于2018-12-05 10:22 被阅读0次

    给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

    示例 1:

    输入: "babad";输出: "bab";注意: "aba" 也是一个有效答案。

    示例 2:

    输入: "cbbd";输出: "bb"

    解答:动态规划法+中心扩展法【回文可以从中心展开,并且只有2n-1个这样的中心,因为字符数为偶数时,回文中心位于处于两字母之间。】时间复杂度为O(n*n)【从头遍历n个字符,每个字符扩展回文需要 O(n)】;空间复杂度为O(1)。

    public static String longestPalindrome(String s) {
            if (s.length() < 1 || s == null) {
                return "";
            }
            int start = 0, end = 0;
            //考虑:str的每一字符 从头开始
            for (int i = 0; i < s.length(); i++) {
                //考虑:str长度为奇数
                int len1 = expandAroundCenter(s, i, i);
                //考虑:str长度为偶数
                int len2 = expandAroundCenter(s, i, i + 1);
                //获取这一字母为中心的回文串的最长长度
                int len = Math.max(len1, len2);
                if (len > end - start) {
                    //获取最长回文串的起始下标 
                    start = i - (len - 1) / 2;
                    //获取最长回文串的终止下标 
                    end = i + len / 2;
                }
            }//substring是左闭右开,所以需要end+1 
            return s.substring(start, end+1);
        }
    
        private static int expandAroundCenter(String s, int left, int right) {
            //奇数时以这一字符为中心,偶数时以这一字符和下一字符为中心,不断向左向右遍历
            while (right < s.length() && left >= 0 && s.charAt(left) == s.charAt(right)) {
                left--;
                right++;
            }
            //返回长度时需要-1,否则溢出
            return right - left - 1;
        }
    

    相关文章

      网友评论

          本文标题:5.最长回文子串

          本文链接:https://www.haomeiwen.com/subject/txkicqtx.html