題目
image.png
和516題很像啊，要連著一起看http://www.itdecent.cn/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] 區(qū)間合法
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);
}
}
