动态规划
class Solution { public: string longestPalindrome(string s) { if(s.size() < 2) return s; int start = 0, maxlen = 1, n = s.size(); vector<vector<int>> dp (n,vector<int>(n)); for(int i = 0; i < n; ++i) dp[i][i] = true; //对角线均为true,因为一个元素肯定是回文子串 for(int j = 1; j < n; ++j) { for(int i = 0; i < j; ++i) { if(s[i] != s[j]) dp[i][j] = false; else { if((j-1) - (i+1) + 1 < 2) dp[i][j] = true; //如果内部区间长度小于等于1 else { if(dp[i+1][j-1]) dp[i][j] = true; //看内部区间是否是回文 } } if(dp[i][j] && j - i + 1 > maxlen) { start = i; maxlen = j - i + 1; } } } return s.substr(start,maxlen); } }; 作者:zrita 链接:https://leetcode-cn.com/problems/longest-palindromic-substring/solution/c-z-by-zrita-19/ 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。