public String longestPalindrome(String s) {
String forwards;
StringBuilder backwards;
int largestIndex = -1;
int curSize = s.length() - 1;
int curIndex = 0;
int totalLength = s.length() - 1;
int indexChecked = 0;
while(curSize >= 0 && largestIndex == -1)
{
while(totalLength - (curIndex + curSize) >= 0)
{
forwards = s.substring(curIndex,curIndex + curSize + 1);
backwards = new StringBuilder(forwards);
backwards.reverse();
if(forwards.equals(backwards.toString()))
{
largestIndex = curIndex;
break;
}
curIndex += curSize;
}
indexChecked++;
if(totalLength - (indexChecked + curSize) < 0 && largestIndex == -1)
{
curSize -= 1;
indexChecked = 0;
}
curIndex = indexChecked;
}
return s.length() == 0 ? "" : s.substring(largestIndex,largestIndex + curSize + 1);
}
my solution currently finds the answer but too slowly to be accepted by leetcode. any ideas on how i can speed it up? the idea behind it is that it starts with a window the size of the entire string, takes that string and reverses it and tries to see if it matches. if it does it returns the match otherwise it shrinks the window and slides it along on progressively smaller window sizes until it detects a palindrome.
Comments
Post a Comment