最长回文子串
给你一个字符串 s
,找到 s
中最长的回文子串。
示例 1:
输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。
示例 2:
输入:s = "cbbd"
输出:"bb"
方法一:中心扩散法
原理:先选定一个字符
首先往左移动,寻找与当前字符相等的字符,直到遇到不相等
然后往右移动,寻找与当前字符相等的字符,直到遇到不相等
最后往左右移动,直到左和右不相等
代码:
public String longestPalindrome(String s) {
int length = s.length();
int left = 0;
int right = 0;
int len = 1;
int maxLen=0;
int maxStart =0;
for (int i = 0; i < length; i++) {
left = i-1;
right = i +1;
while (left >=0 && s.charAt(left) == s.charAt(i)) {
left --;
len++;
}
while (right <length && s.charAt(right) == s.charAt(i)) {
right ++;
len ++;
}
while (left >=0 && right <length && s.charAt(left) == s.charAt(right)) {
left--;
right++;
len +=2;
}
if(len >maxLen) {
maxLen=len;
maxStart = left;
}
len = 1;
}
return s.substring(maxStart+1,maxStart+1+maxLen);
}
方法二:动态规划
这里直接贴一下官方给的方案,主要学习思想
class Solution {
public String longestPalindrome(String s) {
int length = s.length();
if(length == 1) return s;
int maxLength = 1;
int start = 0;
boolean[][] dp = new boolean[length][length];
// 对于单个字符来说,肯定是回文
for (int i = 0; i < length; i++) {
dp[i][i] = true;
}
// L 相当于步长
for(int L =2 ;L<= length;L++ ) {
for(int i=0;i<length;i++) {
int j = i+L-1;
if(j>=length) break;
if(s.charAt(i) != s.charAt(j)) {
dp[i][j] =false;
}else {
if (j - i < 3) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i + 1][j - 1];
}
}
if(dp[i][j] && j-i+1 > maxLength) {
maxLength = j-i+1;
start = i;
}
}
}
return s.substring(start,start+maxLength);
}
}