首页 > 代码库 > Leetcode#5 Longest Palindromic Substring
Leetcode#5 Longest Palindromic Substring
原题地址
以前可以用DP枚举所有回文串，但是Leetcode后来增加了几组大数据，用DP会超时。
什么！用DP都超时了？？那怎么办？
答：二分法尝试可能的回文串长度，直到找到最大值
需要注意的是，假设现在已经验证了长度为length的回文串不存在，传统的二分法就会去尝试长度为length/2的回文串是否存在。但是！长度为length+1的回文串是可能存在的。例如："aba"，虽然长度为2的回文串不存在，但是长度为3的回文串是存在的。根本原因就是奇数回文串的存在性无法推出偶数回文串的存在性，反之也一样。
所以，需要对传统的二分法进行改进，每次把length和length-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 = 1;11 int r = s.length();12 int index = 0;13 int length = 1;14 15 while (l <= r) {16 int m = (l + r) / 2;17 // 尝试长度为m-1的回文串是否存在18 for (int i = 0; i + m - 1 <= s.length(); i++)19 if (palindromep(s, i, i + m - 2)) {20 index = i;21 length = m - 1;22 break;23 }24 // 尝试长度为m的回文串是否存在25 for (int i = 0; i + m <= s.length(); i++)26 if (palindromep(s, i, i + m - 1)) {27 index = i;28 length = m;29 break;30 }31 32 if (length == m || length == m - 1)33 l = m + 1;34 else35 r = m - 2;36 }37 38 return s.substr(index, length);39 }
Leetcode#5 Longest Palindromic Substring
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。