/*
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:
string findLongestPalindrome(string s, int n){
int length= s.length();
if(s.substr(n).length()==1) return s.substr(n);
string prep = findLongestPalindrome(s, n+1);
bool isPalindrome;
for(int i=length-1; i>n && ((i-n+1)>prep.length()); i--){
isPalindrome = true;
for(int j=0; (i-j)>=(n+j); j++){
if(s[n+j]!=s[i-j]){
isPalindrome = false;
break;
}
}
if(isPalindrome){
return s.substr(n, i-n+1);
}
}
return prep;
}
string longestPalindrome(string s) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
return findLongestPalindrome(s, 0);
}
};
No comments:
Post a Comment