题目
image.png
和516题很像啊，要连着一起看https://www.jianshu.com/p/d737ee489b95
题解
暴力解
列举所有的子串，判断是否为回文串，保存最长的回文串
超出时间限制
class Solution {
public String longestPalindrome(String s) {
int n = s.length();
if (n < 2) {
return s;
}
// s[i,j] 是不是回文子串
int len = 1;
String res = s.substring(0, 1);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (solver(s, i, j)) {
// len = Math.max(len, (j - i) + 1);
if (len < (j-i+1)) {
len = j - i + 1;
res = s.substring(i, j+1); // substring
}
}
}
}
return res;
}
private boolean solver(String s, int i, int j) {
while (i < j) {
if (s.charAt(i) != s.charAt(j)) {
return false;
}
i++;
j--;
}
return true;
}
}
题解1
class Solution {
public String longestPalindrome(String s) {
int n = s.length();
if (n < 2) {
return s;
}
// s[i,j] 是不是回文子串
int len = 1;
String res = "";
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (solver(s, i, j)) {
// len = Math.max(len, (j - i) + 1);
if (len < (j-i+1)) {
len = j - i + 1;
res = s.substring(i, j+1); // substring
}
}
}
}
return res;
}
private boolean solver(String s, int i, int j) {
while (i < j) {
if (s.charAt(i) != s.charAt(j)) {
return false;
}
i++;
j--;
}
return true;
}
}
结果
初始化改一下
String res = s.substring(0, 1);
或者
不过，改了之后的解答还是超出时间限制
题解2
dp
image.png
索引问题很麻烦，还是建议申请时用n
// dp[i,j]=dp[i+1,j-1]&&check(i,j)
class Solution {
public String longestPalindrome(String s) {
int n = s.length();
if (n < 2) {
return s;
}
int[][] dp = new int[n + 1][n + 1];
for (int i = 0; i <= n; i++) {
dp[i][i] = 1;
}
int res = 0;
int start = 0;
// 考虑dp[i+1,j-1]的合法性，i+1<j-1, i<j-2
for (int i = n - 1; i > 0; i--) {
for (int j = n; j > i; j--) {
// dp[i][j] = dp[i+1][j-1] && (s.charAt(i-1) == s.charAt(j-1));
if (s.charAt(i-1) == s.charAt(j-1)) { // 注意s的索引和dp的索引不同
// 排除dp[i][i+1]的情况
if (i < j-2) {
dp[i][j] = dp[i+1][j-1];
} else {
dp[i][j] = 1;
}
}
if (dp[i][j] == 1) {
if (j-i+1 > res) {
res = j-i+1;
start = i-1; // 注意s的索引和dp的索引不同
}
}
}
}
return s.substring(start, start + res);
}
}
错误
image.png
初始化res=1
// dp[i,j]=dp[i+1,j-1]&&check(i,j)
class Solution {
public String longestPalindrome(String s) {
int n = s.length();
if (n < 2) {
return s;
}
int[][] dp = new int[n + 1][n + 1];
for (int i = 0; i <= n; i++) {
dp[i][i] = 1;
}
int res = 1;
int start = 0;
// 考虑dp[i+1,j-1]的合法性，i+1<j-1, i<j-2
for (int i = n - 1; i > 0; i--) {
for (int j = n; j > i; j--) {
// dp[i][j] = dp[i+1][j-1] && (s.charAt(i-1) == s.charAt(j-1));
if (s.charAt(i-1) == s.charAt(j-1)) { // 注意s的索引和dp的索引不同
// 排除dp[i][i+1]的情况
if (i < j-2) {
dp[i][j] = dp[i+1][j-1];
} else {
dp[i][j] = 1;
}
}
if (dp[i][j] == 1) {
if (j-i+1 > res) {
res = j-i+1;
start = i-1; // 注意s的索引和dp的索引不同
}
}
}
}
return s.substring(start, start + res);
}
}
参考题解 （推荐）
class Solution {
public String longestPalindrome(String s) {
int n = s.length();
if (n<2) return s;
int[][] dp = new int[n][n];
for (int i=0; i<n; i++){
dp[i][i] = 1;
}
int len=1;
int start=0;
//dp[i][j] = dp[i+1][j-1] s[i]==s[j]
for (int i=n-2; i>=0; i--){
for (int j=i+1; j<n; j++){
if (s.charAt(i)==s.charAt(j)){
// j=i+1时，dp[i][j]应该是1，但是dp表计算的话就是0，需要特别处理
if (j-i<2) dp[i][j]=1; // dp[i+1][j-1] 区间合法
else dp[i][j] = dp[i+1][j-1];
}
if (dp[i][j]==1 && (j-i+1>len)){
len = j-i+1;
start = i;
}
}
}
return s.substring(start, start+len);
}
}
参考题解2
public class Solution {
public String longestPalindrome(String s) {
// 特判
int len = s.length();
if (len < 2) {
return s;
}
int maxLen = 1;
int begin = 0;
// dp[i][j] 表示 s[i, j] 是否是回文串
boolean[][] dp = new boolean[len][len];
char[] charArray = s.toCharArray();
for (int i = 0; i < len; i++) {
dp[i][i] = true;
}
for (int j = 1; j < len; j++) {
for (int i = 0; i < j; i++) {
if (charArray[i] != charArray[j]) {
dp[i][j] = false;
} else {
if (j - i < 3) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i + 1][j - 1];
}
}
// 只要 dp[i][j] == true 成立，就表示子串 s[i..j] 是回文，此时记录回文长度和起始位置
if (dp[i][j] && j - i + 1 > maxLen) {
maxLen = j - i + 1;
begin = i;
}
}
}
return s.substring(begin, begin + maxLen);
}
}
