天河高端网站建设湖南网站设计

动态规划

• 思路：
  • 假设 dp[i][j] 为字符串 (i, j) 子串是否为回文的结果；
  • 那么 dp[i][j] = dp[i + 1][j - 1] 且 (s[i] == s[j])；
  • 长度为1的字符串都是回文；
    • 原字符串长度为1，是回文；
    • 原字符串子串长度为1，即 i = j，dp[i][i] = true；
  • 使用 begin 变量记录最长时的子串左边界，maxLen 缓存最长回文串的长度；
  • 遍历迭代计算出所有 dp[i][j] 的值：
    • 迭代子串长度 len，同时从左边界遍历；

class Solution {
public:string longestPalindrome(string s) {int size = s.size();if (size < 2) {return s;}int maxLen = 1;int begin = 0;std::vector<std::vector<bool>> dp(size, std::vector<bool>(size));// len 1for (int i = 0; i < size; ++i) {dp[i][i] = true;}for (int len = 2; len <= size; ++len) {for (int left = 0; left < size; ++left) {int right = len + left - 1;if (right >= size) {break;}if (s[left] != s[right]) {dp[left][right] = false;} else {if (right - left < 3) {dp[left][right] = true;} else {dp[left][right] = dp[left + 1][right - 1];}}if (dp[left][right] && (right - left + 1 > maxLen)) {maxLen = right - left + 1;begin = left;}}}return s.substr(begin, maxLen);}
};