1.题目
最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：**s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
</pre>
示例 2：
输入：s = "cbbd"
输出："bb"</pre>
2.分析
回文串可能有两种形式：ABA和BBB，这两种都是回文串，都需要考虑到
3.题解
3.1方法一：中心扩散法
思路：中心扩散法顾名思义中心往两边扩散。遍历每个点，从每个点往两边扩散，将这个点作为回文中心判断最长的回文
class Solution {
// s = "babad"
public String longestPalindrome(String s) {
int l = 0;//最长字串左边的位置
int r = 0;//最长字串右边的位置
int len = 0;//最长字串的长度
for (int i = 1; i < s.length(); i++) {
int j = i, k = i;
// ABA型
while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) {
//说明是回文串
if (k - j + 1 > len) {
len = k -j +1;
l = j;
r = k;
}
j--;k++;
}
//AA型
j = i;
k = i;
if (s.charAt(--j) == s.charAt(k)){
// ABA型
while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) {
//说明是回文串
if (k - j + 1 > len) {
len = k -j +1;
l = j;
r = k;
}
j--;k++;
}
}
}
String substring = s.substring(l, r + 1);
return substring;
}
}
3.2动态规划
思路：将一个字符串转化为二维数组，dp[i][j]代表字符串i到j是否是回文。
- 假如l到r之间是回文 那么dp[l][r] = true
- 我们要计算l-1和r+1之间是不是回文，那么就只用计算l-1等不等于r+1就可以知道了
- 1.状态转移方程式
- dp[l][r] = dp[l+1][r-1] && S[l] == S[r]
- 三种情况 ： aba aa c
- 特殊情况l==r的时候，那么一定是回文字符串
-
2.填二维表的时候，从小到大填
image.png
class Solution {
// s = "babad"
public String longestPalindrome(String s) {
int maxL = 0;
int maxR = 0;
int maxV = 0;
Boolean[][] dp = new Boolean[s.length()][s.length()];
//2.将分割线全填true（l == r）(将l=r的情况全部设置为true)
for (int i = 0; i < s.length(); i++) {
dp[i][i] = true;
}
//3.遍历填表格(只填下半部分)
//只填下半部分，但是我们要从最顶上填，因为由于状态转移方程式下一步需要上一步的值（具体见图）
for (int r = 1; r < s.length(); r++) {
for (int l = 0; l < r; l++) {
//4.状态转移方程式 dp[l][r] = dp[l+1][r-1] && s[l] == s[r]
dp[l][r] = s.charAt(l) == s.charAt(r) && (r-l == 1 || dp[l+1][r-1]);
//5.记录最长的回文子串
if (dp[l][r]){
if (r-l+1 > maxV){
maxV = r-l+1;
maxL = l;
maxR = r;
}
}
}
}
return s.substring(maxL,maxR+1);
}
}
4.时空复杂度
- 中心扩散法：
- 时间复杂度：最高n^2
- 空间复杂度：1
- 动态规划：
- 时间复杂度：n^2
- 空间复杂度：n^2
参考链接：
作者：reedfan
链接：https://leetcode.cn/problems/longest-palindromic-substring/solution/zhong-xin-kuo-san-fa-he-dong-tai-gui-hua-by-reedfa/
网友评论