java - 使用递归查找字符串中最长的回文

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)

如何降低时间复杂度？动态规划应该是答案