LeetCode 5. 最长回文子串

5. 最长回文子串

解题思路

• 双指针法：以每个字符为中心，向两边扩散，找到最长的回文子串

  • 具体分奇数长度和偶数长度两种情况

• manacher算法：时间复杂度O(n)，空间复杂度O(n)，适合大数据量的情况

参考代码

class Solution {
    public String longestPalindrome(String s) {
        int startIndex = 0;
        int maxLen = 0;
        
        for(int i = 0; i < s.length(); i ++) {
            // aba
            int left = i;
            int right = i;
            while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
                if(right - left + 1 > maxLen) {
                    maxLen = right - left + 1;
                    startIndex = left;
                }
                left --;
                right ++;
            }
        }

        for(int i = 0; i < s.length(); i ++) {
            int left = i;
            int right = i + 1;
            while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
                if(right - left + 1 > maxLen) {
                    maxLen = right - left + 1;
                    startIndex = left;
                }
                left --;
                right ++;
            }
        }
        return s.substring(startIndex, startIndex + maxLen);
    }
}