Самая длинная палиндромная подстрока на 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/

у вас есть 2 метода грубой силы и оптимизировать