# 5. Longest Palindromic Substring

## 刷题内容

• https://leetcode-cn.com/problems/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:

Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"



## 解题方案

class Solution {
// 采用动态规划
// 如果 i == j ，则只有一个字母 肯定是回文串
// 如果 char[i] == char[j] && j == i + 1 , 两个字母相等 肯定是回文串
// 如果 char[i] == char[j] && j > i + 1 && cache[i+1][j-1]为true，则肯定是回文串
public String longestPalindrome(String s) {
if(s == null || s.length() <2){
return s;
}
boolean[][] cache = new boolean[s.length()][s.length()]; // 记录 i ~ j 是否是回文串
char[] chars = s.toCharArray();
int len = s.length();
int start = 0;
int end = 0;
// 采用至底向上的动态规划，也可以采用递归方式
for(int i = len - 1; i >= 0; i --){
for(int j = i; j < len; j ++){
if(i == j){
cache[i][j] = true;
}else if(j == i + 1 && chars[i] == chars[j]){
cache[i][j] = true;
if(end - start + 1 < 2){
end = j;
start = i;
}
}else if(chars[i] == chars[j] && cache[i + 1][j-1]){
cache[i][j] = true;
if(end - start  < j-i){
start = i;
end = j;
}
}else{
cache[i][j] = false;
}
}
}
return s.substring(start,end+1);
}
}


apachecn/AiLearning