Monday, June 10, 2013

Leetcode: Longest Palindromic Substring in C++


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.
Solution:
void search(string& s, int& left, int& right, int curL, int curR)
    {
        while(curL>=0&&curR<s.size())
        {
                if(s[curL]!=s[curR])
                  break;
                curL--;
                curR++;
        }
        curL++;
        curR--;
        if(curR-curL>right-left)
        {
           left = curL;
       right = curR;
        }
    }
    string longestPalindrome(string s) {
        int maxlength = INT_MIN;
        int left  = 0;
        int right = 0;
        int pos = 0;
        while(pos<s.size()-1)
        {
            search(s, left, right,pos, pos);
            search(s, left, right,pos, pos+1);
            pos++;
        }
        return s.substr(left, right-left+1);
    }

No comments:

Post a Comment