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%。
leetcode-最长回文子串
因为有时间复杂度为O(N)的马拉车算法,上面的解法的时间复杂度O(N^2),本来不应该超过97%,但是上面的代码有一些优化,比如:
if (n - i < maxLength / 2) { break; }

while (right < n - 1 && s.charAt(right) == s.charAt(right + 1)) { right++; }
这样就会比单纯遍历所有的字符中心快。

上一篇:最长连续序列


下一篇:QTextEdit设置可输入字符字节限制