【leetcode hot 100】【5】5. 最长回文子串

题目

给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

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

示例 2：

输入：s = “cbbd”
输出：“bb”

提示：

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

解题思路

动态规划是解决该问题的常用方法，以下是使用动态规划的解题思路：

1. 定义状态
   定义状态 dp[i][j] 表示字符串 s 从 i 到 j 是否为回文串，是则为 true，不是则为 false。

2. 确定状态转移方程
   当 s[i]=s[j] 时，如果 dp[i+1][j-1]=true，则 dp[i][j]=true。因为只有当 i+1 到 j-1 的子串是回文串，并且 s[i]=s[j] 时，i 到 j 的子串才是回文串。
   当 s[i] != s[j] 时，dp[i][j]=false。

3. 初始化状态
   初始化状态为 dp[i][i]=true，表示单个字符是回文串。

4. 求解最长回文子串
   根据状态转移方程求解状态数组 dp，并在求解的过程中记录最长回文子串的位置和长度。具体来说，如果 dp[i][j]=true 且 j-i+1>len，则更新最长回文子串的位置和长度。

5. 返回结果
   根据最长回文子串的位置和长度，返回最长回文子串。

代码

c++

class Solution {
public:string longestPalindrome(string s) {int n = s.size();vector<vector<bool>> dp(n, vector<bool>(n, false));// dp[i][j]表示s[i]到s[j]是否为回文串int start = 0, len = 1; // 记录最长回文子串的起始位置和长度// 初始化状态for (int i = 0; i < n; i++) {dp[i][i] = true; // 单个字符是回文串if (i < n - 1 && s[i] == s[i+1]) {dp[i][i+1] = true; // 两个相邻相同的字符是回文串start = i;len = 2;}}// 状态转移for (int l = 3; l <= n; l++) { // 枚举回文串长度for (int i = 0; i + l - 1 < n; i++) { // 枚举回文串起始位置int j = i + l - 1; // 回文串结束位置if (s[i] == s[j] && dp[i+1][j-1]) {dp[i][j] = true;start = i;len = l;}}}return s.substr(start, len);}
};

golang

func longestPalindrome(s string) string {n := len(s)dp := make([][]bool, n)for i := range dp {dp[i] = make([]bool, n)}// dp[i][j]表示s[i]到s[j]是否为回文串start, maxLen := 0, 1 // 记录最长回文子串的起始位置和长度// 初始化状态for i := 0; i < n; i++ {dp[i][i] = true // 单个字符是回文串if i < n-1 && s[i] == s[i+1] {dp[i][i+1] = true // 两个相邻相同的字符是回文串start = imaxLen = 2}}// 状态转移for l := 3; l <= n; l++ { // 枚举回文串长度for i := 0; i + l - 1 < n; i++ { // 枚举回文串起始位置j := i + l - 1 // 回文串结束位置if s[i] == s[j] && dp[i+1][j-1] {dp[i][j] = truestart = imaxLen = l}}}return s[start:start+maxLen]
}