请教一道leetcode原题： 最长回文子串# JobHunting - 待字闺中
q*1
1 楼
用java写的DP版本的解法，总是超时。改了很多天还是不行，有谁能帮我看下啊？或者
给我一个能通过的DP的O(N2)版本学习一下，（我知道有O(n)的算法）谢谢大家了！
public class Solution {
public String longestPalindrome(String s) {
int n = s.length();
int longestBegin = 0;
int maxLen = 1;
int table[][] = new int[1000][1000];
for (int i = 0; i < n; i++) {
table[i][i] = 1;
}
for (int i = 0; i < n-1; i++) {
if (s.charAt(i) == s.charAt(i+1)) {
table[i][i+1] = 1;
longestBegin = i;
maxLen = 2;
}
}
for (int len = 3; len <= n; len++) {
for (int i = 0; i < n-len+1; i++) {
int j = i+len-1;
if (s.charAt(i) == s.charAt(j) && table[i+1][j-1]==1) {
table[i][j] = 1;
longestBegin = i;
maxLen = len;
}
}
}
return s.substring(longestBegin, longestBegin + maxLen - 1);
}
}
给我一个能通过的DP的O(N2)版本学习一下，（我知道有O(n)的算法）谢谢大家了！
public class Solution {
public String longestPalindrome(String s) {
int n = s.length();
int longestBegin = 0;
int maxLen = 1;
int table[][] = new int[1000][1000];
for (int i = 0; i < n; i++) {
table[i][i] = 1;
}
for (int i = 0; i < n-1; i++) {
if (s.charAt(i) == s.charAt(i+1)) {
table[i][i+1] = 1;
longestBegin = i;
maxLen = 2;
}
}
for (int len = 3; len <= n; len++) {
for (int i = 0; i < n-len+1; i++) {
int j = i+len-1;
if (s.charAt(i) == s.charAt(j) && table[i+1][j-1]==1) {
table[i][j] = 1;
longestBegin = i;
maxLen = len;
}
}
}
return s.substring(longestBegin, longestBegin + maxLen - 1);
}
}
