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 ExceededLast executed input:"eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee...你能告诉我，我有什么问题吗？

Answer 1

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

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;

}

}