当前位置：首页 > news >正文

最长回文子串算法精解（Leetcode热题100，第5题）

news 2026/3/26 17:49:26

题目

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

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

主包能力有限，只讲中心扩散法。如果大家有不同方法，欢迎大家评论。

Python解法

代码示例

class Solution: def longestPalindrome(self,s:str)->str: if not s or len(s) < 1: return s start = end = 0 for i in range(len(s)): len1 = self._expand(s, i, i) len2 = self._expand(s, i, i+1) current_len = max(len1, len2) if current_len > end - start: start = i - (current_len - 1) // 2 end = start + current_len - 1 return s[start:end + 1] def _expand(self,s:str,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

解释

1，首先判断字符串为0，或为1的时候，并初始化左右起始位置。

if not s or len(s) < 1: return s start = end = 0

2，遍历字符串，统一处理回文数为奇数和偶数的情况，并保留最大的长度。

len1 = self._expand(s,i,i) #回文数为奇数情况 len2 = self._expand(s,i,i+1) #回文数为偶数情况 current_len = max(len1, len2)

3，根据长度反推起始位置。

if current_len > end - start: start = i - (current_ len - 1) // 2 end = start + current_len - 1

4，函数部分（核心）

从中心向两边扩张，返回回文串的长度。

while left >= 0 and right < len(s) and s[left] == s[right]: left -= 1 right += 1 return right - left - 1

5，以babad进行演示

索引: 0 1 2 3 4 字符: b a b a d i=0 (b): 奇数中心→ "b" (长度1) 偶数中心→ "" (长度0) 当前最长: "b" i=1 (a): 奇数中心→ "aba" (长度3) 偶数中心→ "" (长度0) 当前最长: "aba" i=2 (b): 奇数中心→ "bab" (长度3) 偶数中心→ "" (长度0) 当前最长: "aba" (或"bab"，长度相同取第一个) i=3 (a): 奇数中心→ "aba" (长度3) 偶数中心→ "" (长度0) i=4 (d): 奇数中心→ "d" (长度1) 偶数中心→ "" (长度0) 最终结果: "aba"

Java解法

代码示例

class Solution { public String longestPalindrome(String s){ if (s == null || s.length() < 1){ return ""; } int start = 0; int end = 0; for (int i=0;i < s.length();i++){ int len1 = expandAroundCenter(s, i, i); int len2 = expandAroundCenter(s, i, i+1); int current_len = Math.max(len1, len2); if (current_len > end -start){ start = i -(current_len - 1) / 2; end = start + current_len -1; } } return s.substring(start, end + 1); } public int expandAroundCenter(String s, int left, int right){ while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){ --left; ++right; } return right - left - 1; } }

解释

整体逻辑仍与python无异，主函数返回时不要直接计算，要使用substring方法计算差值，否则会报错不能正常返回。

C语言解法

代码示例

// 中心扩展辅助函数：返回以left/right为中心的回文子串长度 int expandAroundCenter(char *s, int left, int right, int len) { // 边界检查 + 字符相等时向两侧扩展 while (left >= 0 && right < len && s[left] == s[right]) { left--; right++; } // 返回实际回文长度（退出循环时left/right已越界，需修正） return right - left - 1; } // 核心函数：查找最长回文子串 char* longestPalindrome(char* s) { // 空字符串处理 if (s == NULL || strlen(s) == 0) { char *empty = (char*)malloc(1); empty[0] = '\0'; return empty; } int len = strlen(s); int start = 0, end = 0; // 记录最长回文的起止下标 for (int i = 0; i < len; i++) { // 奇数长度回文（中心为单个字符） int len1 = expandAroundCenter(s, i, i, len); // 偶数长度回文（中心为两个字符之间） int len2 = expandAroundCenter(s, i, i + 1, len); // 取两种情况的最大长度 int current_len = len1 > len2 ? len1 : len2; // 更新最长回文的起止下标 if (current_len > end - start) { start = i - (current_len - 1) / 2; end = i + current_len / 2; } } // 分配内存存储结果（+1 用于存储字符串结束符'\0'） int res_len = end - start + 1; char *result = (char*)malloc(res_len + 1); if (result == NULL) { // 内存分配失败处理 return NULL; } // 拷贝最长回文子串到结果数组 strncpy(result, s + start, res_len); result[res_len] = '\0'; // 手动添加字符串结束符 return result; }