给定一个字符串 s
,找到 s
中最长的回文子串。你可以假设 s
的最大长度为 1000。
示例 1:
输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。
示例 2:
输入: "cbbd" 输出: "bb"
class Solution { public: string longestPalindrome(string s) { if (s.length() == 0) return ""; bool dp[1000][1000] = {{false}}; int max = 0; string ans; for (int x = s.length(); x >= 0; x--) { for (int y = x; y < s.length(); y++) { if (y - x < 2) { dp[x][y] = s[x] == s[y]; } else { dp[x][y] = dp[x + 1][y - 1] && (s[x] == s[y]); } if (dp[x][y] && y - x + 1 > max) { max = y - x + 1; ans = s.substr(x, y - x + 1); } } } return ans; } };
第i到第j个char能否构成回文取决于 1.第i+1到第j-1个char是否回文 2.第i个char和第j个char是否相同 dp[i][j]=dp[i+1][j-1]&&s[i]==s[j] 注意考虑串为空的特殊情况 x自大到小,y从小到大,确保dp[x+1][y-1]已经完成定义
https://leetcode-cn.com/problems/longest-palindromic-substring/