Thursday, May 29, 2014

LeetCode: Longest Palindromic Substring

New Start.
Ignore the Manacher's Algorithm.

Time O(n^2) Space O(1)
Start from center of i or from i, i+1.

public static String longestPalindrome(String s) {
if (s==null || s.length()==0) return null;
if (s.length() == 1) return s;

String longest = s.substring(0, 1);
for (int i = 0; i < s.length(); i++) {
//Get Longest palindrome with center of i
String temp = helper(s, i, i);
if (temp.length() > longest.length()) {
longest = temp;
}
//Get Longest palindrome with center of i, i+1
temp = helper(s,i,i+1);
if (temp.length() > longest.length()) {
longest = temp;
}
}
return longest;
}
private static String helper(String s, int start, int end) {
while (start >=0 && end <= s.length()-1 && s.charAt(start) == s.charAt(end)) {
start--;
end++;
}
return s.substring(start+1, end);
}