亲宝软件园·资讯

展开

Java查找最大回文串 Java实现查找当前字符串最大回文串代码分享

人气:0
想了解Java实现查找当前字符串最大回文串代码讲解的相关内容吗,在本文为您仔细讲解Java查找最大回文串的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:查找最长回文字符串,回文字符串,下面大家一起来学习吧。

先看代码

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="google",如何求其最长的回文子字符串"goog"

1,最简单直接的想法就是:找出字符串的所有子串,然后判断每一个子串是否是回文,并记录,比较求出最大长度的回文,*算法时间复杂度为O(n^3)

/* 
 * 4,求最长回文子串 
 *问题描述:给定一个字符串求出其所有子串中最长的回文子串,例如google字符串,最长子串为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; 
  } 

加载全部内容

相关教程
猜你喜欢
用户评论