题目描述
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
解析
回文子串是指一个字符串从前往后读和从后往前读是相同的。为了找到最长的回文子串，有多种方法，比如动态规划、中心扩展法和Manacher算法。这里我们介绍中心扩展法，因为它的思想比较简单且实现起来也较为容易。
中心扩展法的核心思想是：每一个字符，以及每一对相邻的字符都可以作为回文中心，从中心开始向两边扩展，检查扩展后的字符串是否仍然是回文，并记录最长的回文子串。
- 遍历字符串中的每一个字符，假设当前字符为回文中心。
- 从当前字符开始向两边扩展，检查扩展后的字符串是否为回文。
- 遍历每一对相邻的字符，假设这对字符的中心为回文中心，同样从中心向两边扩展检查。
- 记录并更新最长的回文子串。
以下是Python代码实现方法
def longest_palindrome(s: str) -> str:
if not s or len(s) == 0:
return ""
def expand_around_center(s, left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return s[left + 1:right]
longest = ""
for i in range(len(s)):
# Odd length palindromes
palindrome1 = expand_around_center(s, i, i)
# Even length palindromes
palindrome2 = expand_around_center(s, i, i + 1)
# Update the longest palindrome found
longest = max(longest, palindrome1, palindrome2, key=len)
return longest
# 示例
s = "babad"
print(longest_palindrome(s)) # 输出: "bab"
代码解析
- 函数定义：longest_palindrome(s: str) -> str，输入是一个字符串 s，输出是一个字符串，表示最长的回文子串。
- 辅助函数：expand_around_center(s, left, right)，这个函数用于从中心向两边扩展，检查是否为回文，并返回最长的回文子串。
- 主循环：遍历字符串中的每一个字符，分别以当前字符和当前字符与下一个字符的间隙为中心，调用 expand_around_center 扩展并检查是否为回文。
- 更新最长回文：通过比较当前找到的回文子串和之前记录的最长回文子串的长度，更新最长回文子串。
以下是使用JavaScript语法实现的最长回文子串算法：
function longestPalindrome(s) {
if (!s || s.length === 0) {
return "";
}
function expandAroundCenter(s, left, right) {
while (left >= 0 && right < s.length && s[left] === s[right]) {
left--;
right++;
}
return s.substring(left + 1, right);
}
let longest = "";
for (let i = 0; i < s.length; i++) {
// Odd length palindromes
let palindrome1 = expandAroundCenter(s, i, i);
// Even length palindromes
let palindrome2 = expandAroundCenter(s, i, i + 1);
// Update the longest palindrome found
if (palindrome1.length > longest.length) {
longest = palindrome1;
}
if (palindrome2.length > longest.length) {
longest = palindrome2;
}
}
return longest;
}
// 示例
let s = "babad";
console.log(longestPalindrome(s)); // 输出: "bab"
代码解析
-
函数定义：
- longestPalindrome(s)：这是主函数，接收一个字符串s作为参数，返回s中的最长回文子串。
-
辅助函数：
- expandAroundCenter(s, left, right)：这是一个内部辅助函数，用于从中心向两边扩展，并返回找到的回文子串。它接收三个参数：字符串s，以及要扩展的左右索引left和right。
- 在while循环中，只要left索引不小于0且right索引小于字符串长度，并且s[left]等于s[right]，就继续向两边扩展（即left--和right++）。
- 循环结束后，使用substring方法提取从left + 1到right（不包括right）的子串，即回文子串。
-
主循环：
- 使用for循环遍历字符串s中的每一个字符。
- 对于每个字符，分别以其自身为中心（奇数长度回文）和以其与下一个字符的间隙为中心（偶数长度回文），调用expandAroundCenter函数。
- 将返回的回文子串与当前记录的最长回文子串longest进行比较，如果更长，则更新longest。
-
返回结果：
- 循环结束后，longest中存储的就是最长的回文子串。
- 返回longest作为结果。
-
示例：
- 对于输入字符串"babad"，函数将输出"bab"作为最长回文子串。
这种方法的时间复杂度为O(n^2)，其中n是字符串的长度。对于每个字符，我们可能需要向两边扩展到整个字符串的长度，但在实际应用中，这种方法通常足够高效。
