Нахождение самого длинного палиндрома в строке с помощью рекурсии

Question

Я застрял на том, почему мое решение работает только для некоторых строк.Например, «sdfbananabasdf» вернул бы «bananab», но «dtattarrattatddetartrateedre» работал бы в бесконечном цикле.Заранее спасибо!

public String longestPalindrome(String s) {
    if(isPalindrome(s)) {
        return s;
    }
    String divisionOne = longestPalindrome(s.substring(0,s.length()-1));
    String divisionTwo = longestPalindrome(s.substring(1,s.length()));
    return (divisionOne.length() >= divisionTwo.length()) ? divisionOne : divisionTwo;        
}

private boolean isPalindrome(String s) {
    if(s.length() == 1) {
        return true;
    }
    int count = s.length() / 2;

    if(s.length() % 2 == 1) {
        count++;
    }
    for(int i = 0; i < count; i++) {
        if(s.charAt(i) != s.charAt(s.length() - 1 - i)) {
            return false;
        }
    }
    return true;
}

Answer 1

По существу, временная сложность вашего алгоритма составляет O(2^n)

Допустим, скажем, f(n) - это функция для вычисления палиндрома для строки с длиной n, в худшем случае мы можем видеть, что

f(n) = 2*f(n - 1)
f(n - 1) = 2*f(n - 2)
...
f(1) = 1

-> f(n) сложность времени равна O(2^n)

Таким образом, для длинной строки ваша программа будет работать долго.Как и в примере, строка с 29 символами потребует O (2 ^ 29) или O (5 * 10 ^ 8) операций.

Примечание : на самом деле, каждая операция требует двух дополнительныхОперации substring и isPalindrome, из-за которых сложность времени составляет O (n * 2 ^ n), а не только O (2 ^ n)

Как уменьшить сложность времени?Динамическое программирование должно быть ответом