题目描述:给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1:
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2:
输入: "cbbd"
输出: "bb"
前言:在两三个月前,这道题练过,现在记忆上有点模糊,今天在把这道题刷一遍,巩固一下。
LeetCode上的记录。
解题思路:
1.首先,我们要解题,那么我们就要知道回文串的概念,回文串,我这里就简单的讲一下,就是类似于,ABA,AABB这种,具体的,大家可以自行百度,这个很好理解。再者呢,就是理解子串的概念,子串和子序列容易搞混,希望大家也可以自行百度,要是题都不懂,那么就别说解题了。
2.子串,想到子串,那么我们以前做过的算法题里面有,求出一个字符串的所有子串,然后再一个一个去对比,但是如果用的是这种解法的话,时间复杂度达到了O(n3)这是完全不能忍受的,所以我们要想想怎么优化。
3.优化,我们想一下,首先我们题目要求是要所有子串的,但是求所有子串据我了解的最低的时间复杂度就是O(n2),所以我们把优化方向,放到求解回文串上,如果我们能将求出回文串只要O(1)的复杂度,那么整个题目就可以优化一个量级。
4.实现,我们可以用到动态规划来解,怎么解呢,我们判断一个字符串是不是回文串,那么我们首先要判断,首字母和尾字母是否相等,然后依次向前推。哪么如果我们已经记录了去掉收尾字母的子串是否是回文串,哪不就解决了吗。
代码实现:
public String longestPalindrome(String s) {
if(s.length()<2)return s;
int len = s.length();
char[] chars = s.toCharArray();
boolean[][] dp = new boolean[len][len];
//对于字符本身,它是回文串。
//初始化。
for (int i = 0; i < len; i++) {
dp[i][i] = true;
}
int begin = 0;
int res = 1;
//求所有子串
//这里面求所有子串的方法是有讲究的,间隔是逐渐增大的,为了DP好计算。
for (int i = 0; i < len; i++) {
for (int start = 0, end = i + 1; end < len; end++, start++) {
if (chars[start] == chars[end]) {
if (end - start + 1 <= 3) {
//子串长度小于3,直接设为True
dp[start][end] = true;
} else {
dp[start][end] = dp[start + 1][end - 1];
}
} else {
dp[start][end] = false;
}
if (dp[start][end]) {
int curLen = end - start + 1;
//记录最长的子串
if (curLen > res) {
res = curLen;
begin = start;
}
}
}
}
return s.substring(begin, res + begin);
}
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-palindromic-substring/submissions/