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

Question

在 leetcode 中我试图解决 "Longest Palindromic Substring" 任务。这是代码：

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/

你有两种方法：暴力破解和优化

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;
}
}

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

Longest Palindromic Substring on Java (leetcode)

java

palindrome