关于PHP字符串的一道面试题

题目：给定一个字符串，要求找出其中最长的回文子串。

解题思路：回文串是指正着读和倒着读都一样的字符串。可以使用动态规划的方法来解决这个问题。

首先，定义一个二维数组dp，其中dp[i][j]表示字符串从索引i到索引j的子串是否是回文串。初始时，将dp[i][i]设置为true，表示单个字符是回文串。

然后，遍历字符串，从长度为2的子串开始判断，如果s[i]等于s[j]且dp[i+1][j-1]为true，则dp[i][j]也为true。如果当前子串的长度大于之前记录的最长回文子串的长度，则更新最长回文子串的起始位置和长度。

最后，返回最长回文子串。

以下是PHP代码实现：

function longestPalindrome($s) {
    $n = strlen($s);
    $dp = array_fill(0, $n, array_fill(0, $n, false));
    $start = 0;
    $maxLen = 1;

    for ($i = 0; $i < $n; $i++) {
        $dp[$i][$i] = true;

        for ($j = 0; $j < $i; $j++) {
            if ($s[$i] == $s[$j] && ($i - $j <= 2 || $dp[$j+1][$i-1])) {
                $dp[$j][$i] = true;

                if ($i - $j + 1 > $maxLen) {
                    $maxLen = $i - $j + 1;
                    $start = $j;
                }
            }
        }
    }

    return substr($s, $start, $maxLen);
}

// 测试
$s = "babad";
echo longestPalindrome($s);  // 输出 "bab"

在给定的字符串"babad"中，最长的回文子串是"bab"。

时间复杂度：O(n^2) 空间复杂度：O(n^2)