# LeetCode 5. Longest Palindromic Substring 最长回文子串

## 题目

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

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

Example:

```Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.
```

Example:

```Input: "cbbd"

Output: "bb"
```

## 讲解

1. 首尾两个字符一样
2. 在首尾两个字符之间的字符串也是回文串

1. s.charAt(i) = s.charAt(j)
2. dp[i + 1][j – 1] = true || j – i <= 2

## Java参考代码

```class Solution {
public String longestPalindrome(String s) {
if (s == null || s.length() < 2) {
return s;
}

int length = s.length();

boolean[][] isPalindrome = new boolean[length][length];

int left = 0;
int right = 0;

for (int j = 1; j < length; j++) {
for (int i = 0; i < j; i++) {
boolean isInnerWordPalindrome = isPalindrome[i + 1][j - 1] || j - i <= 2;

if (s.charAt(i) == s.charAt(j) && isInnerWordPalindrome) {
isPalindrome[i][j] = true;

if (j - i > right - left) {
left = i;
right = j;
}
}
}
}

return s.substring(left, right + 1);

// Time Complexity: O(n ^ 2)
// Space Complexity: O(n ^ 2)
}
}```