Time Complexity is O(n^2) Space Complexity is O(1)
Sorry for not Mancher's algorithm, since it is too complicated for me.
public 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 from the center of i
String temp = helper(s,i,i);
if (temp.length() > longest.length()) {
longest = temp;
}
//Get longest palindrome from the center of i, i+1
temp = helper(s,i,i+1);
if (temp.length() > longest.length()) {
longest = temp;
}
}
return longest;
}
private 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);
}
No comments:
Post a Comment