首页 > 代码库 > Longest Palindromic Substring
Longest Palindromic Substring
Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
方法一：暴力破解，计算出所有的回文字串，然后求最长的回文字串，结果。。。。肯定超时
方法二：使用Palindrome Partitioning中的dp方法，依然是dp[i][j]表示以i为起点，j为长度的字串是否是回文，统计的过程中求解最长的回文子串，时间复杂度为O(n2)，代码如下：
1 class Solution { 2 public: 3 string longestPalindrome(string s) { 4 if( s.empty() ) 5 return 0; 6 //vector< vector<bool> > dp(s.length(), vector<bool>(s.length()+1, false)); //如果使用vector，那么会超时 7 const int lens = s.length(); 8 bool dp[lens][lens+1]; //行代表子串起始坐标，列代表字串长度 9 for(int i=0; i<s.length(); ++i) //长度为0，1的子串均认为是回文10 dp[i][0] = dp[i][1] = true;11 int start = 0;12 int len = 1;13 for(int j=2; j<=s.length(); ++j) //从长度为2开始计算14 for(int i=0; i<=s.length()-j; ++i) {15 dp[i][j] = dp[i+1][j-2] && (s[i] == s[i+j-1]);16 if( dp[i][j] && j>len ) { //记录最长回文字串的位置和长度17 start = i;18 len = j;19 }20 }21 return s.substr(start, len);22 }23 };
方法三：Manacher算法，时间复杂度O(n), 空间复杂度O(n)，具体有请度娘，神人也！
Longest Palindromic Substring
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。