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

你的答案是花费了大量的时间来运行。而不是蛮力方法尝试优化它。如果您在处理动态方法时遇到问题，这是一个更好的解决方案：class Solution {public String longestPalindrome(String s) {&nbsp; &nbsp; if(s == null || s.length() < 1)&nbsp; &nbsp; &nbsp; &nbsp; return "";&nbsp; &nbsp; int start = 0;&nbsp; &nbsp; int end = 0;&nbsp; &nbsp; for(int i=0; i<s.length(); i++)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; int l1 = fromMiddle(s,i,i);&nbsp; &nbsp; &nbsp; &nbsp; int l2 = fromMiddle(s,i,i+1);&nbsp; &nbsp; &nbsp; &nbsp; int l = Math.max(l1,l2);&nbsp; &nbsp; &nbsp; &nbsp; if(l > end - start)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; start = i - ((l-1)/2);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; end = i + (l/2);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return s.substring(start, end+1);}public int fromMiddle(String s, int left, int right){&nbsp; &nbsp; if(s == null || left > right)&nbsp; &nbsp; &nbsp; &nbsp; return 0;&nbsp; &nbsp; while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right))&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; left--;&nbsp; &nbsp; &nbsp; &nbsp; right++;&nbsp; &nbsp; }&nbsp; &nbsp; return right-left-1;}}