leetcode-最长回文子串

本文主要是介绍leetcode-最长回文子串，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

leetcode-最长回文子串
给定一个字符串 s，找到 s 中最长的回文子串。

1. 核心思想：中心扩散法，从中间开始向两边扩散来判断回文串。我们以一个字符串的某个下标为中心，朝两边扩散，遍历整个字符串，找到最长的回文子串。

2. 代码：

    public String longestPalindrome(String s) {
        if (s.length() < 2) {
            return s;
        }
        int maxLength = 0;
        int n = s.length();
        int start = 0;
        for (int i = 0; i < n;) {
            //剩余字符串的长度比已找到的最长回文子串的长度一半还小，说明，以剩余字符串的任意一个字符为中心都不可能找到更长的回文子串
            if (n - i < maxLength / 2) {
                break;
            }
            int left  = i;
            int right = i;
            //重复字符，右指针往前走
            while (right < n - 1 && s.charAt(right) == s.charAt(right + 1)) {
                right++;
            }
            //下一个中心就是右指针的下一个
            i = right + 1;
            //开始朝两边扩散
            while (left > 0 && right < n - 1 && s.charAt(left - 1) == s.charAt(right + 1)) {
                left--;
                right++;
            }
            //记录找到的最长子串的起点和长度
            if (right - left + 1 > maxLength) {
                start = left;
                maxLength = right - left + 1;
            }
        }
        return s.substring(start, start + maxLength);
    }

3.最长回文子串的问题解决了，时间复杂度 O(N^2)，空间复杂度 O(1)。
在leetcode上面跑，超过了97%。

因为有时间复杂度为O(N)的马拉车算法，上面的解法的时间复杂度O(N^2)，本来不应该超过97%，但是上面的代码有一些优化，比如：
if (n - i < maxLength / 2) { break; }
和
while (right < n - 1 && s.charAt(right) == s.charAt(right + 1)) { right++; }
这样就会比单纯遍历所有的字符中心快。

这篇关于leetcode-最长回文子串的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！