5. Longest Palindromic Substring
难度: Medium
刷题内容
原题连接
- 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:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:
Input: "cbbd"
Output: "bb"
解题方案
思路 1 **- 时间复杂度: O(n^2)*- 空间复杂度: O(n^2)***
使用动态规划的思路,用一个二维数组cache[i][j]记录i到j是否为回文串, beats 54.36%
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);
}
}
