首页 > 代码库 > Leetcode#5 Longest Palindromic Substring
Leetcode#5 Longest Palindromic Substring
原题地址
最初的想法是用动态规划，令palin[i][j]表示s[i..j]是否是回文串，则有递推公式palin[i][j] = s[i] == s[j] && palin[i+1][j-1]。因为递推式只使用相邻层的值，所以编码的时候可以将二维状态数组压缩成一维的。
代码：
1 string longestPalindrome(string s) { 2 if (s.empty()) 3 return ""; 4 5 vector<bool> palinp(s.length(), true); 6 int start = 0; 7 int len = 1; 8 9 for (int i = s.length() - 2; i >= 0; i--) {10 palinp[i] = true;11 for (int j = s.length() - 1; j > i; j--) {12 palinp[j] = s[i] == s[j] && palinp[j - 1];13 if (palinp[j] && j - i + 1 > len) {14 len = j - i + 1;15 start = i;16 }17 }18 }19 20 return s.substr(start, len);21 }
虽然看上去挺好，但DP的时间复杂度是O(n^2)，跟蛮力算法差不多，果然，对于大数据超时了。
这个时候就到了二分法大显身手的时刻了！
二分法枚举回文串的长度，如果找到了，长度翻倍并继续尝试，如果没找到，长度折半并继续。
需要注意的是，奇数长度的回文串和偶数长度的回文串的存在性是相互独立的，如果长度为n的偶数串不是回文串不存在，并不代表长度为n+1的奇数串不是回文串，反之亦然。例如"ab"不是回文串，而"aba"是回文串。所以，在二分枚举的时候，每次都要把奇数长度和偶数长度都枚举一下（m和m-1）以确保正确。
代码：
1 bool palindromep(string &s, int i, int j) { 2 while (i < j && s[i] == s[j]) { 3 i++; 4 j--; 5 } 6 return i >= j; 7 } 8 9 string longestPalindrome(string s) {10 int l = 2;11 int r = s.length();12 int start = 0;13 int len = 1;14 15 while (l <= r) {16 int m = (l + r) / 2;17 for (int i = 0; i + m <= s.length(); i++)18 if (palindromep(s, i, i + m - 1)) {19 start = i;20 len = m;21 break;22 }23 for (int i = 0; i + (m - 1) <= s.length(); i++)24 if (palindromep(s, i, i + (m - 1) - 1)) {25 start = i;26 len = max(len, m - 1);27 break;28 }29 if (m - len <= 1)30 l = m + 1;31 else32 r = m - 1;33 }34 35 return s.substr(start, len);36 }
Leetcode#5 Longest Palindromic Substring
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。