Java 上最长的回文子字符串 (leetcode)

Question

在leetcode中，我试图解决"最长的回文子字符串"任务。这是代码：

public String longestPalindrome(String s) {
String str = "";
for(int i = 0; i < s.length(); i++)
{
for(int j = 1 + i; j < s.length() + 1; j++)
{
String sub = s.substring(i, j);
if(isPalindrome(sub) && sub.length() > str.length())
{
str = s.substring(i, j);
}
}
}
return str;
}
public static boolean isPalindrome(String s)
{
if(s.length() < 2)
return true;
else
for(int i = 0; i < s.length() / 2; i++)
{
if(!(s.charAt(i) == s.charAt(s.length() - 1 - i)))
return false;                   
}
return true;            
}

当我在 Eclipse 中运行它时它可以工作，但是当我想将解决方案提交到 leetcode 时，它向我显示一个错误：

Submission Result: Time Limit Exceeded
Last executed input:
"eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee...

你能告诉我，我的问题是什么吗？

Answer 1

您的代码对于leetcode花费了太多时间

for(int j = 1 + i; j < s.length() + 1; j++){
String sub = s.substring(i, j);
if(isPalindrome(sub) && sub.length() > str.length()){
str = s.substring(i, j);
}
}

在这个循环中，你调用 2 次 s.substring(i， j(;你可以从调用它 1 次开始

for(int j = 1 + i; j < s.length() + 1; j++){
String sub = s.substring(i, j);
if(isPalindrome(sub) && sub.length() > str.length()){
str = sub;
}
}

然后你可以在互联网上搜索：

https://www.geeksforgeeks.org/longest-palindrome-substring-set-1/

您有 2 种方法暴力破解和优化

Answer 2

你的答案是需要花费大量的时间来运行。而不是蛮力方法尝试优化它。 如果您在处理动态方法时遇到问题，这是一个更好的解决方案：

class Solution {
public String longestPalindrome(String s) {
if(s == null || s.length() < 1)
return "";
int start = 0;
int end = 0;
for(int i=0; i<s.length(); i++)
{
int l1 = fromMiddle(s,i,i);
int l2 = fromMiddle(s,i,i+1);
int l = Math.max(l1,l2);
if(l > end - start)
{
start = i - ((l-1)/2);
end = i + (l/2);
}
}
return s.substring(start, end+1);
}
public int fromMiddle(String s, int left, int right)
{
if(s == null || left > right)
return 0;
while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right))
{
left--;
right++;
}
return right-left-1;
}
}