[LeetCode]5.最长回文子串
文章目录
题目描述
给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。
示例 1:
输入: "babad"
输出: "bab"
注意: "aba"也是一个有效答案。
示例 2:
输入: "cbbd"
输出: "bb"
分析
刚开始拿到这道题的时候,感觉毫无头绪,如果采用暴力破解的话,时间复杂度是O(n3),有点太高了。后来网上搜了一些文章,提到可以用动态规划的方法。因为一个字符天然是一个回文串,而两个字符只要相同,那它们在一起也构成一个回文串。而以此类推,三个字符的串只要首尾两个字符相同就是回文串。继续往上推,如果一个字符串,它处于首尾两个字符之间的子串是回文串,并且它的首尾字符相同,则它就是一个回文串。因此只需要用一个二维数组,第一维是字符串的第一个字符的下标,第二维是尾字符的下标。用这样一个二维数组来缓存结果,就可以在枚举输入字符串的所有子串的时候,根据之前缓存的结果快速地判断当前的子串是否是回文串。
实现代码如下
class Solution {
public String longestPalindrome(String s) {
char[] in = s.toCharArray();
int stringLen = s.length();
boolean[][] len = new boolean[stringLen][stringLen];
int start = 0;
int end = 0;
for(int i = 0; i < stringLen; i++) {
for(int j = 0; j < stringLen - i; j++) {
if(i == 0) {
len[j][j] = true;
} else if(i == 1) {
if(in[j] == in[j + 1]) {
len[j][j + 1] = true;
}
} else {
if(in[j] == in[j + i] && len[j + 1][j + i - 1]) {
len[j][j + i] = true;
}
}
if(len[j][j + i] == true) {
start = j;
end = j + i;
}
}
}
return s.substring(start, end + 1);
}
}

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论