AC截图

题目

思路

1. 初始化DP表：

   • 创建一个大小为 n x n 的二维布尔数组 dp，其中 dp[i][j] 表示字符串 s 从第 i 个字符到第 j 个字符的子串是否为回文。

   • 初始化所有长度为1的子串为回文，即 dp[i][i] = true。

2. 处理长度为2的子串：

   • 如果相邻的两个字符相同，则它们构成一个回文子串。更新 dp[i][i+1] 和相应的 start 和 maxLength。

3. 按长度递增顺序填充DP表：

   • 从长度为3开始，逐步增加子串长度，直到达到字符串的总长度。

   • 对于每个可能的子串长度 len，遍历所有可能的起始点 i 和对应的结束点 j（注意 j = i + len - 1 必须在字符串范围内）。

   • 使用状态转移方程 dp[i][j] = (s[i] == s[j] && dp[i+1][j-1]) 更新 dp 数组的值。如果 s[i] == s[j] 并且去掉两端字符后的子串也是回文，则当前子串是回文。

4. 记录最长回文子串信息：

   • 在每次发现一个新的更长的回文子串时，更新最长回文子串的起始位置和长度。

5. 返回结果：

   • 最后根据记录的 start 和 maxLength 提取并返回最长的回文子串。

代码

class Solution {
public:string longestPalindrome(string s) {int n = s.size();if(n<2) return s;vector<vector<bool>> dp(n,vector<bool>(n));for(int i=0;i<n;i++){dp[i][i] = true;}int maxLen = 1;int start = 0;for(int i=0;i<n-1;i++){if(s[i]==s[i+1]){dp[i][i+1] = true;start = i;maxLen = 2;}}for(int len=3;len<=n;len++){for(int i=0;i<n;i++){int j = i+len-1;if(j>n) break;if(s[i]==s[j] && dp[i+1][j-1]){dp[i][j] = true;start = i;maxLen = len;}}}return s.substr(start,maxLen);}
};