ps建设网站步骤,郴州信息港网站,wordpress插件 乱码,dede网站模板 医疗class Solution {
public:string longestPalindrome(string s) {// 获取输入字符串的长度int n s.size();// 如果字符串长度为1#xff0c;直接返回原字符串#xff0c;因为任何单个字符都是回文串if (n 1)return s;// 创建一个二维数组dp#xff0c;用于记录子串是否为回…
class Solution {
public:string longestPalindrome(string s) {// 获取输入字符串的长度int n s.size();// 如果字符串长度为1直接返回原字符串因为任何单个字符都是回文串if (n 1)return s;// 创建一个二维数组dp用于记录子串是否为回文串vectorvectorbool dp(n, vectorbool(n, false));// 定义两个循环变量i和ji表示子串的起始位置j表示子串的结束位置int i, j;// 初始化结果字符串为一个任意字符长度为1string result a;// 从字符串的末尾开始向前遍历for (i n - 1; i 0; i--) {for (j i; j n; j) {// 情况1子串只包含一个字符一定是回文串if (i j)dp[i][j] true;// 情况2子串包含两个字符判断这两个字符是否相等else if (i j - 1) {if (s[i] s[j]) {dp[i][j] true;// 更新结果字符串为当前长度更长的子串result result.size() (j - i 1)? s.substr(i, j - i 1): result;}}// 情况3子串长度大于2判断首尾字符是否相等并且去掉首尾字符的子串是回文串else {if (s[i] ! s[j])continue;dp[i][j] dp[i 1][j - 1];if (dp[i][j] true) {// 更新结果字符串为当前长度更长的子串result result.size() (j - i 1)? s.substr(i, j - i 1): result;}}}}// 返回找到的最长回文子串return result;}
};时间和空间复杂度都为O(n²)还是不是非常好。
