题目地址

https://leetcode.com/problems/longest-palindromic-substring/description/

题目描述

5. Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:

Input: "cbbd"
Output: "bb"

思路

基于中心点枚举的算法.
从中间往两边.
关键是走两遍.
左右不是同一个, 和左右是同一个.
O(n)2.

关键点

代码

语言支持：Java

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        
        int start = 0, length = 0, max = 0;
        for (int i = 0; i < s.length(); i++) {
            length = findPalindrome(s, i, i);
            if (length > max) {
                max = length;
                start = i - length / 2;
            }
            
            length = findPalindrome(s, i, i + 1);
            if (length > max) {
                max = length;
                start = i - length / 2 + 1;
            }
        }
        
        return s.substring(start, start + max);
    }
    
    private int findPalindrome(String s, int left, int right) {
        int length = 0;
        while (left >= 0 && right < s.length()) {
            if (s.charAt(left) != s.charAt(right)) {
                break;
            }
            
            if (left == right) {
                length += 1;
            } else {
                length += 2;
            }
            
            left--;
            right++;
        }
        
        return length;
    }
}