//https://leetcode-cn.com/problems/longest-palindromic-substring/submissions/ //中心扩展法 class Solution { public: string longestPalindrome(string s) { int n = s.size(); if (n < 2) return s; int left_max = 0, right_max = -1; for (int i = 0; i < n; ++i) { int left = i, right = i; while (left >= 0 && s[left] == s[i]) --left; while (right < n && s[right] == s[i]) ++right; while (left >= 0 && right < n && s[left] == s[right]) { ++right; --left; } if (right - left > right_max - left_max) { right_max = right; left_max = left; } } return s.substr(left_max + 1, right_max - left_max - 1); } }; //动态规划法 class Solution { public: string longestPalindrome(string s) { int n = s.size(); if (n < 2) return s; // dp[i][j]标记从i到j是否是回文子串 vector<vector<int>> dp(n, vector<int>(n)); string ans; // length表示判断的子串的长度 // left表示字串的左边起始位置 // right表示字串的右边终止位置 for(int length = 0; length < n; length++) { for(int left = 0; left + length < n; left++) { int right = left + length; if(length == 0) dp[left][right] = 1; else if(length == 1) dp[left][right] = (s[left] == s[right]); else dp[left][right] = (s[left] == s[right] && dp[left + 1][right - 1]); if(dp[left][right] && (length + 1) > ans.size()) ans = s.substr(left, length + 1); } } return ans; } };