【Hot 100 刷题计划】LeetCode 5. 最长回文子串 | C++ 动态规划题解

LeetCode 5. 最长回文子串 | C 动态规划题解 题目描述题目级别中等给你一个字符串s找到s中最长的回文子串。回文串是指正着读和反着读都一样的字符串。 解题思路动态规划 (Dynamic Programming)寻找最长回文子串的核心在于一个长回文串去掉首尾字符后剩下的部分依然是一个回文串。基于这个特性我们可以使用动态规划来记录和推导状态。1. 状态定义我们定义一个二维数组dp其中dp[j][i]dp[j][i]dp[j][i]表示字符串s从索引jjj到索引iii的子串是否为回文串。如果是回文串则dp[j][i]1dp[j][i] 1dp[j][i]1或true。如果不是则dp[j][i]0dp[j][i] 0dp[j][i]0或false。2. 状态转移方程当我们遍历字符串考察首尾两个字符s[j]s[j]s[j]和s[i]s[i]s[i]时如果s[j]s[i]s[j] s[i]s[j]s[i]我们需要判断去掉首尾字符后的内部子串是否也是回文串子串长度≤3\le 3≤3即i−j≤2i - j \le 2i−j≤2比如aa或aba。只要首尾字符相等它必然是回文串。子串长度3 33此时是否为回文串取决于内部子串的状态即dp[j1][i−1]dp[j1][i-1]dp[j1][i−1]是否为 1。如果s[j]≠s[i]s[j] \neq s[i]s[j]s[i]那么该子串显然不是回文串。3. 记录最长状态我们在更新dp数组的过程中随时记录最长回文子串的起始位置init和最大长度li最后直接通过substr截取返回即可。 C 代码实现classSolution{public:stringlongestPalindrome(string s){intns.size();if(n2)returns;// 长度为 0 或 1 的字符串直接返回intli1;// 记录最长回文子串的长度至少为 1intinit0;// 记录最长回文子串的起始索引// dp[j][i] 表示 s[j...i] 是否是回文串vectorvectorintdp(n,vectorint(n,0));// i 作为右边界j 作为左边界进行遍历for(inti1;in;i){for(intj0;ji;j){// 如果首尾字符相等if(s[j]s[i]){// 情况1子串长度为 2 或 3if(i-j1||i-j2){dp[j][i]1;}// 情况2子串长度大于 3由内部子串决定elseif(dp[j1][i-1]!0){dp[j][i]1;}// 如果当前是回文串且长度大于之前记录的最大长度则更新if(dp[j][i]1(i-j1li)){lii-j1;initj;}}}}returns.substr(init,li);}};