第五题：最长回文子串(Longest Palindromic Substring)

本文主要是介绍第五题：最长回文子串(Longest Palindromic Substring)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述：

给定一个字符串 s，找到 s 中最长的回文子串。

示例：

1. 输入：s = "babad"
   输出："bab" 或 "aba"

2. 输入：s = "cbbd"
   输出："bb"

要求： 你需要找出 s 中的最长回文子串。

解题思路

方法1：中心扩展法

回文字符串的特点是对称的，因此我们可以从每个字符（或字符间隙）作为中心，向两边扩展来找到回文子串。

1. 遍历每个字符：对于字符串中的每个字符，尝试以该字符作为回文的中心进行扩展，检查最长回文子串。

2. 扩展中心：

   • 对于每个字符，尝试以其为中心，分别考虑回文长度为奇数和偶数的情况。
   • 对于奇数长度回文，以字符本身为中心进行扩展。
   • 对于偶数长度回文，以字符和其下一个字符之间的位置为中心进行扩展。

3. 更新最长回文子串：在扩展过程中，更新记录当前找到的最长回文子串的起始位置和长度。

C 语言实现

#include <stdio.h>
#include <string.h>char* longestPalindrome(char* s) {int n = strlen(s);if (n == 0) return "";int start = 0, maxLen = 1;// Helper function to expand around centervoid expandAroundCenter(int left, int right) {while (left >= 0 && right < n && s[left] == s[right]) {if (right - left + 1 > maxLen) {start = left;maxLen = right - left + 1;}left--;right++;}}for (int i = 0; i < n; i++) {expandAroundCenter(i, i); // Odd length palindromesexpandAroundCenter(i, i + 1); // Even length palindromes}char* result = (char*)malloc((maxLen + 1) * sizeof(char));strncpy(result, s + start, maxLen);result[maxLen] = '\0';return result;
}

Java 实现

public class Solution {public String longestPalindrome(String s) {if (s == null || s.length() == 0) return "";int start = 0, maxLen = 1;// Helper function to expand around centerString expandAroundCenter(String s, int left, int right) {while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {left--;right++;}return s.substring(left + 1, right);}for (int i = 0; i < s.length(); i++) {String oddLenPalindrome = expandAroundCenter(s, i, i);String evenLenPalindrome = expandAroundCenter(s, i, i + 1);String longerPalindrome = oddLenPalindrome.length() > evenLenPalindrome.length() ? oddLenPalindrome : evenLenPalindrome;if (longerPalindrome.length() > maxLen) {maxLen = longerPalindrome.length();start = s.indexOf(longerPalindrome);}}return s.substring(start, start + maxLen);}
}

Python 实现

def longestPalindrome(s: str) -> str:def expandAroundCenter(left: int, right: int) -> str:while left >= 0 and right < len(s) and s[left] == s[right]:left -= 1right += 1return s[left + 1:right]if not s:return ""start, max_len = 0, 1for i in range(len(s)):# Odd length palindromespal1 = expandAroundCenter(i, i)# Even length palindromespal2 = expandAroundCenter(i, i + 1)# Determine the longer palindromelonger_pal = pal1 if len(pal1) > len(pal2) else pal2if len(longer_pal) > max_len:start = i - (len(longer_pal) - 1) // 2max_len = len(longer_pal)return s[start:start + max_len]

时间复杂度

时间复杂度： 所有这些实现方法的时间复杂度为 (O(n^2))，其中 (n) 是字符串 s 的长度。虽然扩展中心的过程对于每个字符都需要进行最多 (O(n)) 次操作，但由于要遍历每个字符，所以总体复杂度是 (O(n^2))。

空间复杂度： 每个实现的空间复杂度为 (O(1)) 除了输出空间（用于存储回文子串）。

这篇关于第五题：最长回文子串(Longest Palindromic Substring)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---