Java完成查找以後字符串最年夜回文串代碼分享

Java完成查找以後字符串最年夜回文串代碼分享。本站提示廣大學習愛好者：（Java完成查找以後字符串最年夜回文串代碼分享）文章只能為提供參考，不一定能成為您想要的結果。以下是Java完成查找以後字符串最年夜回文串代碼分享正文

先看代碼

public class MaxHuiWen {
 
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    String s = "abb";
    MaxHuiWen(s);
  }
   
  //1.輸入回文串
  public static void MaxHuiWen(String s){
    //存儲字符串的長度
    int length = s.length();
    //存儲最長的回文串
    String MaxString = "";
    //遍歷以後字符串的一切子串
    for(int i = 0 ; i < length ; i++){
      for(int j = i ; j < length + 1 ; j++){
        String s1 = s.substring(i , j);
        //假如以後字符串為回文串而且年夜於MaxString的長度，就調換以後MaxString
        if(HuiWen(s1) && s1.length() > MaxString.length()){
            MaxString = s1;
        }
        //System.out.println(s1);
      }
    }  
    //假如MaxString長度年夜於等於2，解釋是回文串
    if(MaxString.length() >= 2){
      System.out.println(MaxString);
    }
    else{
      System.out.println("沒有回文串");
    }
     
  }
   
  //2.斷定字符串能否為回文串
  public static boolean HuiWen(String s){
    boolean flag = true;
    int length = s.length();
    char s1[] = s.toCharArray();
    //早年，從後，遍歷字符串，停止比擬
    for(int i = 0 , j = length - 1 ; i <= j ; i++ , j--){
      if(s1[i] != s1[j]){
        flag = false;
      }
    }
    return flag;
  }
   
}

一，字符串的回文斷定

斷定一個字符串能否為回文

成績描寫，給定一個字符串，如String T="madam";要斷定該字符串能否為回文

辦法一：1，界說兩個字符串元素指針(留意java沒有指針的概念)，int right=T.length()-1 ;int left=0;

2，即left從右邊開端，right從左邊開端，順次比擬所指的字符能否相等，若相等，則將left++，right--；不然，直接前往不是回文

while(left<right){

if（T.charAt(left)!=T.charAt(right)）

return false;

left++;

right--;

}

return true;

代碼：

/* 
   * 3： 
   * 回文斷定 
   * 成績描寫：回文，英文palindrome，指一個順著讀和反過去讀都一樣的字符串，好比madam、我愛我， 
   * 辦法一： 
   * 剖析：應用兩個"指針"分離從字符串頭和尾掃描，若每個"指針"所指值都相等，這為回文 
   */ 
  public boolean isPalindrome(String s){ 
    if(s==null) 
      return false; 
    int left=0; 
    int right=s.length()-1; 
    while(left<right){ 
      if(s.charAt(left)!=s.charAt(right)) 
        return false; 
      left++; 
      right--; 
    } 
    return true; 
  } 

辦法二：回文字符串如"madam",若將其全體反轉，則照樣獲得其自己"madam",在將兩個字符串比擬，若相等，則為回文

1，完成一個將字符串反轉的函數

/* 
 * 完成一個字符串的反轉函數 
 */ 
private String reverse(String str){ 
  String strResult=""; 
  for(int i=str.length()-1;i>=0;i--){ 
    strResult+=str.charAt(i); 
  } 
  return strResult; 
} 
2，關於目的字符串s，起首將其反轉temp=reverse(s)，然後在斷定temp.equals(s)
/*
* 將字符串顛倒，再與原字符串停止比擬，若相等，則為回文，不然不是
* 算法時光龐雜度為O(n)
*/
public boolean isPalindrome2(String s){
String temp=reverse(s);
if(s.equals(temp))
return true;
else
return false;
}

二：若何求一個給定字符串的最年夜回文字符串

例如，給定字符串String T="谷歌",若何求其最長的回文子字符串"goog"

1，最簡略直接的設法主意就是：找出字符串的一切子串，然後斷定每個子串能否是回文，並記載，比擬求出最年夜長度的回文，*算法時光龐雜度為O(n^3)

/* 
 * 4,求最長回文子串 
 *成績描寫：給定一個字符串求出其一切子串中最長的回文子串，例如谷歌字符串，最長子串為goog 
 *剖析： 
 *1，最簡略直接的設法主意就是：找出字符串的一切子串，然後斷定每個子串能否是回文，並記載，比擬求出最年夜長度的回文 
 *算法時光龐雜度為O(n^3) 
 */ 
public String longestPalindrome1(String s){ 
  String result=null; 
  String tempString=""; 
  //界說最長回文子串的長度 
  int max=0; 
  //遍歷字符串中的一切元素 
  for(int i=0;i<s.length();i++){ 
    //數組下標指針j從字符串前面開端往前遍歷 
    for(int j=s.length()-1;j>i;j--){ 
      //斷定每個字符串時刻為回文 
      tempString=s.subStr( i, j+1); 
      //假如tempString是回文子串而且其長度(j-i+1)>max 
      if(isPalindrome(tempString)&&(j-i+1)>max){ 
        max=j-i+1; 
        result=subString(i, j+1); 
      } 
    } 
  } 
  return result; 
} 

2，第二種思緒就是關於字符串中的每個字符T[i]，斷定 

以T[i]，T[i+1]為中間的偶數長度子字符串是回文 

T[i]為中間的奇數長度子字符串能否是回文 

public String longestPalindrome2(String T){ 
    String result=null; 
    //寄存最年夜回文字符串的長度 
    int max=0; 
    //遍歷每個字符，以每個字符為中間斷定奇偶擴大子串 
    for(int i=0;i<T.length();i++){ 
      //界說兩個數組下標指針，以i，i+1為中間的偶子序列 
      int pStart=i; 
      int pEnd=i+1; 
      while(pStart>=0&&pEnd<=(T.length()-1)&&T.charAt(pStart)==T.charAt(pEnd)){ 
        pStart--; 
        pEnd++; 
      } 
      //假如子字符串的長度>max，則暫存為最長子回文串 子回文串的長度=(pEnd-1)-(pStart+1)-1=pEnd-pStart-1 
      if(pEnd-pStart-1>max){ 
        max=pEnd-pStart-1; 
        result=subString( pStart+1, pEnd-1+1); 
      } 
       
      //以i為中間，斷定擴大奇序列能否為回文串 
      pStart=i-1; 
      pEnd=i+1; 
      while(pStart>=0&&pEnd<=(T.length()-1)&&T.charAt(pStart)==T.charAt(pEnd)){ 
        pStart--; 
        pEnd++; 
      } 
      if (pEnd-pStart-1>max) { 
        max=pEnd-pStart-1; 
        result=subStrint(T, pStart+1, pEnd-1+1); 
      } 
    } 
    return result; 
  }