3 - Longest Palindromic Substring

发布时间:2017-1-20 0:55:18 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"3 - Longest Palindromic Substring",主要涉及到3 - Longest Palindromic Substring方面的内容,对于3 - 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. class Solution { public: bool isfPalindrome(string s, int curIndex, int maxLen) { bool ifPal = false; if( (curIndex-maxLen+1) < 0 || (curIndex+maxLen-1) >= s.length()) return ifPal; int i = maxLen - 1; int left = curIndex - i; int right = curIndex + i; while(i>0 && s.at(left) == s.at(right)) { i --; left = curIndex - i; right = curIndex + i; } if(i == 0) ifPal = true; return ifPal; } string longestPalindrome(string s) { // Start typing your C/C++ solution below // DO NOT write int main() function if(s.length()<2) return s; int maxIndex = 0; int maxLen = 1; string newStr = "#"; for(int index = 0 ; index < s.length(); index++) { newStr = newStr + s.at(index) + "#"; } for (int index = 1; index < newStr.length(); index++) { if( isfPalindrome(newStr,index,maxLen) ) //if it is more or equal to longgest Palindrome { maxIndex = index; int left = index - maxLen; int right = index + maxLen; while(left >=0 && right < newStr.length() && newStr.at(left) == newStr.at(right)) { maxLen++; left = index - maxLen; right = index + maxLen; } } } string result = ""; int start = maxIndex - maxLen +1; int end = maxIndex + maxLen -1; for(int i = start; i <= end; i++) { if(newStr.at(i) != '#') result += newStr.at(i); } return result; } };

上一篇:淘宝核心系统团队博客
下一篇:POJ 1731 下一个全排列

相关文章

相关评论