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);
}
Labels:
String/Number
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment