Thursday, February 28, 2013

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.

*/
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