力扣--动态规划5.最长回文子串

class Solution {
public:string longestPalindrome(string s) {// 获取输入字符串的长度int n = s.size();// 如果字符串长度为1，直接返回原字符串，因为任何单个字符都是回文串if (n == 1)return s;// 创建一个二维数组dp，用于记录子串是否为回文串vector<vector<bool>> dp(n, vector<bool>(n, false));// 定义两个循环变量i和j，i表示子串的起始位置，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²)，还是不是非常好。