Wednesday, July 22, 2015

longest palindromic string -- Leetcode

Question:

Write a function that finds the longest palindromic substring in a string.
ex: findLongstPal('affaptbbcracecarf') returns 'racecar'

Answer:

string findLongstHelp(string str, int& maxi, int& maxj){
    int len = str.length();
    bool flag[] = new int[len+1];
    int max=0;
   
    for (int i = 0;i<len+1;++i){
       flag[i] = i;
    }
 
    for(int i=len;i>=0;--i){
        for(int j=i;j>=0;--j){  
            if(isPalindrome(str, j, i)){
                int diff = i-j+1;            
                if(diff >= i-flag[i]){
                    flag[i] = j;
                }
            }
        }
     
        if(i-flag[i] > max){
            maxi = i;
            maxj = flag[i];
        }
         
    }
    return str.substring(maxj,maxi-maxj+1);

}

bool isPalindrome(string str, int m, int n){
     while(m<n){
        if(str[m] != str[n]) break;
        m++;
        n--;
     }
     if(m<n) return false;
     return true;
}
     

No comments:

Post a Comment