当前位置： 面试刷题>> 最长回文子串 (经典算法题500道)
### 题目描述
给定一个字符串 `s`，找到 `s` 中最长的回文子串。你可以假设 `s` 的最大长度为 1000。
**回文子串** 是指一个字符串从前往后读和从后往前读是完全相同的字符串。
### 示例
**输入**: "babad"
**输出**: "bab" 或 "aba"
**输入**: "cbbd"
**输出**: "bb"
### PHP 示例代码
```php
function longestPalindrome($s) {
$n = strlen($s);
if ($n < 2) {
return $s;
}
$start = 0;
$maxLength = 1;
// 辅助函数，用于检查回文
function expandAroundCenter($left, $right, $s) {
while ($left >= 0 && $right < strlen($s) && $s[$left] == $s[$right]) {
$left--;
$right++;
}
return strlen($s) - $right + $left + 1;
}
// 遍历所有可能的中心
for ($i = 0; $i < $n - 1; $i++) {
// 奇数长度回文
$len1 = expandAroundCenter($i, $i, $s);
// 偶数长度回文
$len2 = expandAroundCenter($i, $i + 1, $s);
$len = max($len1, $len2);
// 如果当前长度大于已知的最大长度，则更新
if ($len > $maxLength) {
$start = $i - floor(($len - 1) / 2);
$maxLength = $len;
}
}
return substr($s, $start, $maxLength);
}
// 测试示例
echo longestPalindrome("babad"); // 输出: bab 或 aba
echo longestPalindrome("cbbd"); // 输出: bb
```
### Python 示例代码
```python
def longestPalindrome(s: str) -> str:
if len(s) < 2:
return s
start, maxLength = 0, 1
def expandAroundCenter(left: int, right: int) -> int:
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return right - left - 1
for i in range(len(s) - 1):
# 奇数长度回文
len1 = expandAroundCenter(i, i)
# 偶数长度回文
len2 = expandAroundCenter(i, i + 1)
max_len = max(len1, len2)
if max_len > maxLength:
start = i - (max_len - 1) // 2
maxLength = max_len
return s[start:start + maxLength]
# 测试示例
print(longestPalindrome("babad")) # 输出: bab 或 aba
print(longestPalindrome("cbbd")) # 输出: bb
```
### JavaScript 示例代码
```javascript
function longestPalindrome(s) {
let start = 0, maxLength = 1;
function expandAroundCenter(left, right) {
while (left >= 0 && right < s.length && s[left] === s[right]) {
left--;
right++;
}
return right - left - 1;
}
for (let i = 0; i < s.length - 1; i++) {
let len1 = expandAroundCenter(i, i); // 奇数长度
let len2 = expandAroundCenter(i, i + 1); // 偶数长度
let len = Math.max(len1, len2);
if (len > maxLength) {
start = i - Math.floor((len - 1) / 2);
maxLength = len;
}
}
return s.substr(start, maxLength);
}
// 测试示例
console.log(longestPalindrome("babad")); // 输出: bab 或 aba
console.log(longestPalindrome("cbbd")); // 输出: bb
```
**码小课网站中有更多相关内容分享给大家学习**，希望这些示例代码能帮助到你！