[LeetCode] Longest Palindromic Substring

Problems:Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

Solution 1: Acceptable O(n^3)

 

public class Solution {
    public String longestPalindrome(String s) {
        if(s == null || s.length() == 1)
            return s;      
        int len = s.length();
        char [] set = s.toCharArray();
        int max = 1;
        int end = 0;
        for( int i=1; i< len;i++){
         for(int t= i-max; t>=0;t--){
          if(isP(set,t,i)){
           max = i-t+1;
           end = i;
          }
         }
        }
        return s.substring(end-max+1,end+1);
    }
    public boolean isP(char [] set, int s, int e){
 if(s<0 || s>e)
   return false;
 int i = 0;
 while((s+i) < (e-i)){
   if(set [ s+i] != set[e-i]){
     return false;
   }
   i++;
 }
 return true;
    }
}

Solution 2: O(n^2)

public class Solution {
  public String longestPalindrome(String s) {
    if (s == null || s.isEmpty()) {
 return null;
    }
 
    if (s.length() == 1) {
 return s;
    }
 
    String longest = s.substring(0, 1);
    for (int i = 0; i < s.length(); i++) {
      String tmp = helper(s, i, i);// odd
      if (tmp.length() > longest.length())
        longest = tmp;
 

      tmp = helper(s, i, i + 1); // even
      if (tmp.length() > longest.length()) 
        longest = tmp;  
    }
    return longest;
  }
 
  public String helper(String s, int begin, int end) {
    while (begin >= 0 && end <= s.length() - 1 && s.charAt(begin) == s.charAt(end)) {
 begin--;
 end++;
    }
    return s.substring(begin + 1, end);
  }
}
Note:The concept uses center to get longestPalindrome is a simple and smart way