每日一题-5. 最长回文子串(20200521)

迷南。 2023-02-11 04:40 10阅读 0赞

今天是2020年5月21日，星期四。

### 题目描述 ###

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

示例 1：

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

示例 2：

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

### 题目思路 ###

在本篇中，小编只介绍「中间扩展法」，其他方法大家可以在LeetCode题解区自取。

「中间扩展法」:从每一个位置出发，向左向右扩散。第一步，先验证left、right位置的字符与当前字符是否相同，不断变换left与right的值，直到left、right位置的字符与当前字符不同。第二步，比较left、right位置的字符是否相同，直到不同为止。

在每次扩散的过程中，都会形成一个窗口，窗口大小为len。如果当前的len > maxLen，则maxLen = len。因为题目要求最终需要输出最长的回文串，所以需要记录maxLen对应的回文串的起始位置，即maxStartIndex = left。

### 参考代码 ###

class Solution {
        public String longestPalindrome(String s) {
            int length = s.length();
            if (s == null || length == 0) {
                return "";
            }
    
            int left = 0;
            int right = 0;
            int len = 1;
            int maxStartIndex = 0;
            int maxLen = 0;
    
            for (int i = 0; i < length; i++) {
                left = i - 1;
                right = i + 1;
                // 从当前中心向左侧扩展，判断是否left位置的字符与当前位置的字符相同
                while (left >= 0 && s.charAt(left) == s.charAt(i)) {
                    left--;
                    len++;
                }
                // 从当前中心向右侧扩展，判断是否right位置的字符与当前位置的字符相同
                while (right < length && s.charAt(right) == s.charAt(i)) {
                    right++;
                    len++;
                }
                // 上面两个循环处理掉了与当前位置字符相同的字符，然后处理left与right位置上字符相同的情况
                while (left >= 0 && right < length && s.charAt(right) == s.charAt(left)) {
                    left--;
                    right++;
                    len = len + 2;
                }
                if (len > maxLen) {
                    maxLen = len;
                    maxStartIndex = left;
                }
                len = 1;
            }
    
            return s.substring(maxStartIndex + 1, maxStartIndex + maxLen + 1);
        }
    }