php - 算法的时间复杂度 : find length of a longest palindromic substring

Question

我编写了一个小的 PHP 函数来查找字符串的最长回文子串的长度。为了避免许多循环，我使用了递归。

算法背后的思想是，遍历数组并针对每个中心(包括字符之间和字符上的中心)递归检查左右插入符值是否相等。当字符不相等或插入符号之一超出数组(单词)范围时，特定中心的迭代结束。

问题:

1) 能否请您写一个数学计算来解释该算法的时间复杂度？根据我的理解，它的复杂度为 O(n^2)，但我正在努力通过详细计算来确认这一点。

2)您如何看待这个解决方案，有什么改进建议(考虑到它是在 45 分钟内写成的，只是为了练习)？从时间复杂度的角度来看，是否有更好的方法？

为了简化示例，我删除了一些输入检查(更多内容在评论中)。

谢谢大家，干杯。

<?php
/**
 * Find length of the longest palindromic substring of a string.
 *
 * O(n^2)
 * questions by developer
 * 1) Is the solution meant to be case sensitive? (no)
 * 2) Do phrase palindromes need to be taken into account? (no)
 * 3) What about punctuation? (no)
 */

$input = 'tttabcbarabb';
$input2 = 'taat';
$input3 = 'aaaaaa';
$input4 = 'ccc';
$input5 = 'bbbb';
$input6 = 'axvfdaaaaagdgre';
$input7 = 'adsasdabcgeeegcbgtrhtyjtj';

function getLenRecursive($l, $r, $word)
{
    if ($word === null || strlen($word) === 0) {
        return 0;
    }

    if ($l < 0 || !isset($word[$r]) || $word[$l] != $word[$r]) {
        $longest = ($r - 1) - ($l + 1) + 1;
        return !$longest ? 1 : $longest;
    }

    --$l;
    ++$r;

    return getLenRecursive($l, $r, $word);
}

function getLongestPalSubstrLength($inp)
{
    if ($inp === null || strlen($inp) === 0) {
        return 0;
    }

    $longestLength = 1;
    for ($i = 0; $i <= strlen($inp); $i++) {
        $l = $i - 1;
        $r = $i + 1;
        $length = getLenRecursive($l, $r, $inp); # around char
        if ($i > 0) {
            $length2 = getLenRecursive($l, $i, $inp); # around center
            $longerOne = $length > $length2 ? $length : $length2;
        } else {
            $longerOne = $length;
        }
        $longestLength = $longerOne > $longestLength ? $longerOne : $longestLength;
}

    return $longestLength;
}

echo 'expected: 5, got: ';
var_dump(getLongestPalSubstrLength($input));
echo 'expected: 4, got: ';
var_dump(getLongestPalSubstrLength($input2));
echo 'expected: 6, got: ';
var_dump(getLongestPalSubstrLength($input3));
echo 'expected: 3, got: ';
var_dump(getLongestPalSubstrLength($input4));
echo 'expected: 4, got: ';
var_dump(getLongestPalSubstrLength($input5));
echo 'expected: 5, got: ';
var_dump(getLongestPalSubstrLength($input6));
echo 'expected: 9, got: ';
var_dump(getLongestPalSubstrLength($input7));

Answer 1

您的代码实际上并不需要递归。一个简单的 while 循环就可以了。是的，复杂度是 O(N^2)。您有 N 个选项来选择中点。递归步数从 1 到 N/2。所有的总和是 2 * (N/2) * (n/2 + 1)/2，也就是 O(N^2)。

对于代码审查，我不会在这里进行递归，因为它相当简单，而且您根本不需要堆栈。我会用 while 循环替换它(仍然在一个单独的函数中，以使代码更具可读性)。