义乌网站建设方式,白云区做网站,织梦视频网站源码,国家工商局官网动态规划
思路#xff1a; 假设 dp[i][j] 为字符串 (i, j) 子串是否为回文的结果#xff1b;那么 dp[i][j] dp[i 1][j - 1] 且 (s[i] s[j])#xff1b;长度为1的字符串都是回文#xff1b; 原字符串长度为1#xff0c;是回文#xff1b;原字符串子串长度为1#xff…动态规划
思路 假设 dp[i][j] 为字符串 (i, j) 子串是否为回文的结果那么 dp[i][j] dp[i 1][j - 1] 且 (s[i] s[j])长度为1的字符串都是回文 原字符串长度为1是回文原字符串子串长度为1即 i jdp[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::vectorstd::vectorbool dp(size, std::vectorbool(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);}
};
