Question Description
Screen Shot 2016-10-11 at 15.23.33.png
My Code
public class Solution {
public String longestPalindrome(String s) {
String ret = String.valueOf(s.charAt(0));
int length = s.length();
if (length <= 1) return s;
boolean shouldBreak = false;
for (int i = length / 2; i > 0; i--) {
int a = i - 1, b = i + 1;
while (a >= 0 && b < length) {
if (s.charAt(a) == s.charAt(b)) {
if (a == 0 || b == length - 1) {
String tmp = s.substring(a, b + 1);
if (tmp.length() > ret.length()) ret = tmp;
shouldBreak = true;
break;
}
a--;
b++;
} else {
String tmp = s.substring(a + 1, b);
if (tmp.length() > ret.length()) ret = tmp;
break;
}
}
a = i - 1;
b = i;
while (a >= 0 && b < length) {
if (s.charAt(a) == s.charAt(b)) {
if (a == 0 || b == length - 1) {
String tmp = s.substring(a, b + 1);
if (tmp.length() > ret.length()) ret = tmp;
break;
}
a--;
b++;
} else {
String tmp = s.substring(a + 1, b);
if (tmp.length() > ret.length()) ret = tmp;
break;
}
}
if (shouldBreak) {
shouldBreak = false;
break;
}
}
for (int i = length / 2; i < length - 1; i++) {
int a = i - 1, b = i + 1;
while (a >= 0 && b < length) {
if (s.charAt(a) == s.charAt(b)) {
if (a == 0 || b == length - 1) {
String tmp = s.substring(a, b + 1);
if (tmp.length() > ret.length()) ret = tmp;
shouldBreak = true;
break;
}
a--;
b++;
} else {
String tmp = s.substring(a + 1, b);
if (tmp.length() > ret.length()) ret = tmp;
break;
}
}
a = i;
b = i + 1;
while (a >= 0 && b < length) {
if (s.charAt(a) == s.charAt(b)) {
if (a == 0 || b == length - 1) {
String tmp = s.substring(a, b + 1);
if (tmp.length() > ret.length()) ret = tmp;
break;
}
a--;
b++;
} else {
String tmp = s.substring(a + 1, b);
if (tmp.length() > ret.length()) ret = tmp;
break;
}
}
if (shouldBreak) {
break;
}
}
return ret;
}
}
Test Result
Screen Shot 2016-10-11 at 15.29.52.png
Solution
For each character and gar between two characters, assume it is the center of a palindromic String. Explore its left and right to get the longest palindromic String. Stop looping if the exploration hits left boundary or the right boundary. Start looping from the center of given String to shorten the total time consumption.
