当前位置： 面试刷题>> 最长回文子串(经典算法150题)
### 题目描述
**最长回文子串**
给定一个字符串 `s`，找到 `s` 中最长的回文子串。你可以假设 `s` 的最大长度为 1000。
**回文子串** 是指正着读和反着读都一样的字符串。
### 示例
**输入**: "babad"
**输出**: "bab"
**注意**: "aba" 也是一个有效答案。
**输入**: "cbbd"
**输出**: "bb"
### 解题思路
为了找到最长的回文子串，我们可以采用多种方法，包括中心扩展法、动态规划法和Manacher算法。这里我们将展示中心扩展法和动态规划法的实现。
### 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++;
}
// 注意返回的是长度，所以需要加1
return $R - $L - 1;
}
// 测试
echo longestPalindrome("babad"); // 输出 "bab" 或 "aba"
```
### Python 实现
#### 动态规划
```python
def longestPalindrome(s: str) -> str:
n = len(s)
if n < 2:
return s
max_len = 1
start = 0
dp = [[False] * n for _ in range(n)]
for i in range(n):
dp[i][i] = True
for j in range(1, n):
for i in range(0, j):
if s[i] == s[j] and (j - i < 2 or dp[i + 1][j - 1]):
dp[i][j] = True
if j - i + 1 > max_len:
max_len = j - i + 1
start = i
return s[start:start + max_len]
# 测试
print(longestPalindrome("babad")) # 输出 "bab" 或 "aba"
```
### 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"
```
以上三种语言的实现均涵盖了中心扩展法和动态规划法的思想，用于解决最长回文子串问题。希望这些代码示例能够帮助你更好地理解和解决该问题。