LeetCode 5. 最长回文子串

Categories:

Tags:

题目描述
思路分析
1. 解法一：中心扩展法（推荐）
2. 解法二：动态规划
相似题目

题目描述

✅ 5. 最长回文子串

题目：

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

示例 1：

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

示例 2：

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

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母组成

思路分析

解法一：中心扩展法（推荐）

核心思路：

回文中心可能是一个字符（奇数长度）或两个字符之间（偶数长度）。

以每个位置为中心向两侧扩展，得到该中心的最长回文。

遍历所有中心，取最长结果。

复杂度分析：

时间复杂度：O(n^2)，其中 n 表示字符串长度。

空间复杂度：O(1)，仅使用常数额外空间。

class Solution {
    public String longestPalindrome(String s) {
        String res = "";
        for (int i = 0; i < s.length(); i++) {
            String s1 = expand(s, i, i);
            String s2 = expand(s, i, i + 1);
            if (s1.length() > res.length()) {
                res = s1;
            }
            if (s2.length() > res.length()) {
                res = s2;
            }
        }
        return res;
    }

    private String expand(String s, int l, int r) {
        // 以 l 和 r 为中心向两侧扩展
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            l--;
            r++;
        }
        return s.substring(l + 1, r);
    }
}

func longestPalindrome(s string) string {
	res := ""
	for i := 0; i < len(s); i++ {
		s1 := expandAroundCenter(s, i, i)
		s2 := expandAroundCenter(s, i, i+1)
		if len(s1) > len(res) {
			res = s1
		}
		if len(s2) > len(res) {
			res = s2
		}
	}
	return res
}

func expandAroundCenter(s string, i, j int) string {
	// 以 i 和 j 为中心向两侧扩展
	for i >= 0 && j < len(s) && s[i] == s[j] {
		i--
		j++
	}
	return s[i+1 : j]
}

解法二：动态规划

核心思路：

用 dp[i][j] 表示 s[i..j] 是否为回文串。

若 s[i] == s[j] 且 j - i <= 2，必为回文；否则依赖 dp[i+1][j-1]。

逆序枚举 i、正序枚举 j，保证子问题已计算。

复杂度分析：

时间复杂度：O(n^2)，其中 n 表示字符串长度。

空间复杂度：O(n^2)，其中 n 表示字符串长度。

public class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 2) {
            return s;
        }

        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        int start = 0;
        int maxLen = 1;

        // 逆序枚举 i，正序枚举 j，确保 dp[i+1][j-1] 已计算
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (j - i <= 2) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                    if (dp[i][j] && (j - i + 1) > maxLen) {
                        start = i;
                        maxLen = j - i + 1;
                    }
                }
            }
        }

        return s.substring(start, start + maxLen);
    }
}

func longestPalindrome(s string) string {
	if len(s) < 2 {
		return s
	}

	n := len(s)
	dp := make([][]bool, n)
	for i := range dp {
		dp[i] = make([]bool, n)
	}

	start := 0
	maxLen := 1

	// 逆序枚举 i，正序枚举 j，确保 dp[i+1][j-1] 已计算
	for i := n - 1; i >= 0; i-- {
		for j := i; j < n; j++ {
			if s[i] == s[j] {
				if j-i <= 2 {
					dp[i][j] = true
				} else {
					dp[i][j] = dp[i+1][j-1]
				}
				if dp[i][j] && (j-i+1) > maxLen {
					start = i
					maxLen = j - i + 1
				}
			}
		}
	}

	return s[start : start+maxLen]
}

相似题目

题目	难度	考察点
9. 回文数	简单	数学、回文检测
125. 验证回文串	简单	字符串处理
131. 分割回文串	中等	回溯、动态规划
132. 分割回文串 II	困难	动态规划
266. 回文排列	简单	哈希表、回文检测
267. 回文排列 II	中等	回溯、字符串
214. 最短回文串	困难	字符串、KMP算法
336. 回文对	困难	字典树、哈希表
647. 回文子串	中等	动态规划、中心扩展
680. 验证回文串 II	简单	双指针、字符串

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/44872862