leetcode： 5. 最长回文子串

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

5. 最长回文子串

题目链接https://leetcode.cn/problems/longest-palindromic-substring/

题目描述

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"        
输出: "bab"        
注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd"        
输出: "bb"

题目解析

首先，我们需要定义什么是回文字符串。回文字符串就是从左往右读和从右往左读都是一样的字符串。例如，“racecar” 就是回文字符串，“level” 也是一个回文字符串。

值得注意的是，一个回文字符串去除首尾两个元素之后，仍然是回文字符串。

基于这一性质，我们可以用动态规划来解决这个问题。动态规划的核心思想是将问题分解成子问题，逐步求解并存储结果，从而避免重复计算。

动态规划解法

我们首先定义一个二维数组 dp，其中 dp[i][j] 表示 s[i:j+1] 是否为回文字符串。

如果 i == j，那么 dp[i][j] = True，因为单个字符总是回文的。

如果 i > j 或 s[i] != s[j]，则 dp[i][j] = False，因为回文字符串的首尾字符必须相同。

如果 i < j 且 s[i] == s[j]，那么 dp[i][j] 的值取决于 dp[i+1][j-1] 的值。如果 dp[i+1][j-1] 是回文，则 dp[i][j] 也是回文。

依据此，我们可以写出状态转移方程：

当 s[i] == s[j] 时：
dp[i][j] = dp[i+1][j-1]

在 s[i]!= s[j]时：
dp[i][j] = False

需要特别注意的是，当 s[i] == s[j] 且 j - i == 1 时，即子串长度为 2，此时两个字符相同即表示该子串是回文，因此 dp[i][j] = True。

在填充 dp 数组时，我们需要注意遍历的顺序。由于 dp[i][j] 依赖于 dp[i+1][j-1]，因此不能按照行遍历，而应该按列遍历。

当dp[i][j]为True时，我们需要判断其是否为当前最长的回文子串，并记录当前的最长回文子串。

代码实现

class Solution {
public:string longestPalindrome(string s) {int n=s.size();auto dp=vector<vector<bool>> (n,vector<bool>(n));int left=0,lenMax=1;for(int i=0;i<n;i++){dp[i][i]=true;}for(int j=1;j<n;j++){for(int i=0;i<j;i++){if(s[i]==s[j]){if(i+1==j||dp[i+1][j-1]){dp[i][j]=true;if(j-i+1>lenMax){lenMax=j-i+1;left=i;}}}}}return s.substr(left, lenMax);;}
};

class Solution(object):def longestPalindrome(self, s):n=len(s)left=0lenMax=1dp=[[False]*n for _ in range (n)]for k in range(0,n):dp[k][k]=Truefor j in range (1,n):for i in range (0,j):if s[i]==s[j]:if i+1==j or dp[i+1][j-1]:dp[i][j]=Trueif j-i+1>lenMax:lenMax=j-i+1left=ireturn s[left:left+lenMax]

func longestPalindrome(s string) string {n:=len(s)dp:=make([][]bool,n)left,lenMax:=0,1for i:=range dp{dp[i]=make([]bool,n)dp[i][i]=true}for j:=1;j<n;j++{for i:=0;i<j;i++{if(s[i]==s[j]){if(j==i+1||dp[i+1][j-1]){dp[i][j]=trueif(j-i+1>lenMax){lenMax=j-i+1left=i}}}}}return s[left:left+lenMax]
}