Longest Palindromic Substring

题：

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
找最小回文字符串
Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

>Example 2:/
Input: "cbbd"
Output: "bb"

暴力brute force

时间复杂度O(N3), 两层循环遍历字符串O(N2),查询字符串是否回文O(N)
这是时间复杂度，真的是太暴力

java暴力
public class longestPalindrome {
   public static void main (String[] args){
       String res = longestPalindrome("babad");
       System.out.println(res);
       //String s = "asdedfg";
   }
   
   public static String longestPalindrome(String s) {
       String result = "";
       String tmp;
       for(int i = 0;i < s.length();i++){
           for(int j = s.length()-1 ; j>= i;j--){
               tmp = s.substring(i, j + 1);
               if(getRoll(tmp) && tmp.length() > result.length()){
               result = tmp;
                   break;
               }
           }
       }
       return result;
   }
   
   public static Boolean getRoll(String s){
       if(s.length() <= 1){
           return true;
       }
       int i = 0;
       int j = s.length() -1 ;
       for( ; j> i ;i++,j--){
           if(s.charAt(i) != s.charAt(j)){
               return false;
           }
       }
       return true;
   }
}

 //i,j 两个指针，前后开始循环arr，arr的子集判断是不是回文
 function longestPalindrome($strInput) {
     $arrInput = str_split($strInput);
     $arrLongestPali = [];
     for($i = 0;$i < count($arrInput) ; $i++){
         for($j = count($arrInput) - 1;$j >= $i; $j--){ //用>= 是为了防止输入为一个字符
             $arrTmp = array_slice($arrInput,$i,($j-$i+1));
             if(getRoll($arrTmp) && count($arrTmp) > count($arrLongestPali)){
                 $arrLongestPali = $arrTmp;
                 break;//j的循环找到了，不必再继续
             }
         }
     }
     $strLongest = implode("",$arrLongestPali);
     return $strLongest;
 }

 //判断一个array是不是回文("aba")
 function getRoll($arrInput){
     if(!$arrInput){
         return true;
     }
     for($i=0,$j = count($arrInput) - 1 ; $j > $i ; $i++,$j--){
         if($arrInput[$i] != $arrInput[$j]){
             return false;
         }
     }
     return true;
 }
 $s = longestPalindrome("babad");
 var_dump($s);

中心点往外扩散

总的时间复杂度是O(N2)。 检测一个中心点的时间是O(N),遍历了一遍字符串，所以总时间是O(N2)
参考：https://blog.csdn.net/gatieme/article/details/50889546

    public static String longestPalindrome(String s) {
    String result = "";
        String tmp;
        for(int i = 0;i < s.length();i++){
            tmp = getRoll(s,i,i);
            if(tmp.length() > result.length()){
                result = tmp;
            }
            
            tmp = getRoll(s,i,i+1);
            if(tmp.length() > result.length()){
                result = tmp;
            }
            
        }
        return result;
    }
    
    public static String getRoll(String s,int start,int end){
            String res = "";
            for(;start >= 0 && end < s.length();start--,end++){
                if(s.charAt(start) == s.charAt(end)){
                    res = s.substring(start,end+1);
                }else{
                    break;
                }
            }
            return res;
    }