给出一个字符串（假设长度最长为1000），求出它的最长回文子串，你可以假定只有一个满足条件的最长回文串。 您在真实的面试中是否遇到过这个题？ Yes 样例： 给出字符串 “abcdzdcab”，它的最长回文子串为 “cdzdc”。 挑战 ： O( n2 ) 时间复杂度的算法是可以接受的，如果你能用 O(n) 的算法那自然更好。
#ifndef C200_H #define C200_H #include<iostream> #include<string> #include<vector> using namespace std; class Solution { public: /* * @param s: input string * @return: the longest palindromic substring */ string longestPalindrome(string s) { // write your code here int len = s.size(); int start=0; int maxLength = 1; if (len <= 1) return s; vector<vector<bool>> dp(len, vector<bool>(len,false)); for (int i = 0; i < len; ++i) dp[i][i] = true; for (int i = 0; i < len - 1; ++i) { if (s[i] == s[i + 1]) { dp[i][i + 1] = true; start = i; maxLength = 2; } } for (int k = 3; k <= len; ++k) { for (int i = 0; i < len - k + 1; ++i) { int j = k + i - 1; if (s[i] == s[j] && dp[i + 1][j - 1]) { dp[i][j] = true; start = i; maxLength = k; } } } return s.substr(start, maxLength); } }; #endif