Monday, June 2, 2014

LeetCode LongestPalindrome

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