当前位置： 面试刷题>> 最长回文串 (经典算法题500道)
### 题目描述补充
题目：**最长回文子串**
给定一个字符串 `s`，找到 `s` 中最长的回文子串。你可以假设 `s` 的最大长度为 1000。
**示例 1**:
```
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
```
**示例 2**:
```
输入: "cbbd"
输出: "bb"
```
### PHP 示例代码
```php
function longestPalindrome($s) {
$n = strlen($s);
if ($n < 2) {
return $s;
}
$start = 0;
$maxLength = 1;
for ($i = 0; $i < $n - 1; $i++) {
// 奇数长度的回文
$len1 = expandAroundCenter($s, $i, $i);
// 偶数长度的回文
$len2 = expandAroundCenter($s, $i, $i + 1);
// 取两种情况的较大者
$len = max($len1, $len2);
// 如果当前找到的回文子串比之前找到的更长，则更新起始位置和最大长度
if ($len > $maxLength) {
$start = $i - floor(($len - 1) / 2);
$maxLength = $len;
}
}
return substr($s, $start, $maxLength);
}
function expandAroundCenter($s, $left, $right) {
$L = $left;
$R = $right;
while ($L >= 0 && $R < strlen($s) && $s[$L] == $s[$R]) {
$L--;
$R++;
}
// 注意，循环结束后，L 和 R 已经越界，所以长度需要加 1 后再减 2
return $R - $L - 1;
}
// 示例用法
echo longestPalindrome("babad"); // 输出: bab 或 aba
```
### Python 示例代码
```python
def longestPalindrome(s: str) -> str:
if len(s) < 2:
return s
start, max_length = 0, 1
for i in range(len(s)):
# 奇数长度的回文
len1 = expandAroundCenter(s, i, i)
# 偶数长度的回文
len2 = expandAroundCenter(s, i, i + 1)
# 保留最大长度回文的起始位置和长度
max_len = max(len1, len2)
if max_len > max_length:
start = i - (max_len - 1) // 2
max_length = max_len
return s[start:start + max_length]
def expandAroundCenter(s: str, left: int, right: int) -> int:
L, R = left, right
while L >= 0 and R < len(s) and s[L] == s[R]:
L -= 1
R += 1
return R - L - 1
# 示例用法
print(longestPalindrome("babad")) # 输出: bab 或 aba
```
### JavaScript 示例代码
```javascript
function longestPalindrome(s) {
let start = 0, maxLength = 1;
const n = s.length;
if (n < 2) return s;
function expandAroundCenter(left, right) {
let L = left, R = right;
while (L >= 0 && R < n && s[L] === s[R]) {
L--;
R++;
}
return R - L - 1;
}
for (let i = 0; i < n - 1; i++) {
const len1 = expandAroundCenter(i, i); // 奇数长度
const len2 = expandAroundCenter(i, i + 1); // 偶数长度
const 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
```
**码小课** 网站中有更多关于算法和数据结构的相关内容分享，包括视频教程、代码实现、解题技巧等，欢迎大家学习交流。