DESCRIPTION:
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example:
Input: "babad"Output: "bab"Note: "aba" is also a valid answer.
Example:
Input: "cbbd"Output: "bb"
ANALYSIS:
When I first saw this problem, some wrong ideas up to me. So, I asked SLF for some hints.
Then, I followed his thought and code for almost one hour and finally AC.
- Loop 'i' is the index of the middle of palindromic substring, and expand to left and right one by one at the same time
- One point should be pay attention to is that, the middle index of palindromic substring can be .5. For example, 'abba', its middle index is 1.5.
- I am disappointed in my speed in solve the index range of 'l' and 'r'. It takes me a lot of time to implement the code without some bugs like indexOutOfBoundException. Maybe it reminds me to practice more.
SOLUTION:
public static String longestPalindrome(String s) {
String longestString="";
for(double i=0.5;i<s.length()-1;i=i+1){
double l=i-0.5;
double r=i+0.5;
while(l>=0&&r<s.length()&&s.charAt((int) l)==s.charAt((int) r)){
l--;r++;
}
l++;r--;
String string=s.substring((int)l,(int)r+1);
if(string.length()>longestString.length())
longestString=string;
}
for(int i=0;i<s.length();i++){
int l=i;
int r=i;
while (l>=0&&r<s.length()&&s.charAt(l)==s.charAt(r)) {
l--;r++;
}
l++;r--;
String string=s.substring(l,r+1);
if(string.length()>longestString.length())
longestString=string;
}
return longestString;
}