Java实现查找当前字符串最大回文串代码分享
先看代码
publicclassMaxHuiWen{
publicstaticvoidmain(String[]args){
//TODOAuto-generatedmethodstub
Strings="abb";
MaxHuiWen(s);
}
//1.输出回文串
publicstaticvoidMaxHuiWen(Strings){
//存储字符串的长度
intlength=s.length();
//存储最长的回文串
StringMaxString="";
//遍历当前字符串的所有子串
for(inti=0;i<length;i++){
for(intj=i;j<length+1;j++){
Strings1=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.判断字符串是否为回文串
publicstaticbooleanHuiWen(Strings){
booleanflag=true;
intlength=s.length();
chars1[]=s.toCharArray();
//从前，从后，遍历字符串，进行比较
for(inti=0,j=length-1;i<=j;i++,j--){
if(s1[i]!=s1[j]){
flag=false;
}
}
returnflag;
}
}
一，字符串的回文判断
判断一个字符串是否为回文
问题描述，给定一个字符串，如StringT="madam";要判断该字符串是否为回文
方法一：1，定义两个字符串元素指针(注意java没有指针的概念)，intright=T.length()-1;intleft=0;
2，即left从左边开始，right从右边开始，依次比较所指的字符是否相等，若相等，则将left++，right--；否则，直接返回不是回文
while(left<right){
if（T.charAt(left)!=T.charAt(right)）
returnfalse;
left++;
right--;
}
returntrue;
代码：
/*
*3：
*回文判断
*问题描述：回文，英文palindrome，指一个顺着读和反过来读都一样的字符串，比如madam、我爱我，
*方法一：
*分析：使用两个"指针"分别从字符串头和尾扫描，若每一个"指针"所指值都相等，这为回文
*/
publicbooleanisPalindrome(Strings){
if(s==null)
returnfalse;
intleft=0;
intright=s.length()-1;
while(left<right){
if(s.charAt(left)!=s.charAt(right))
returnfalse;
left++;
right--;
}
returntrue;
}
方法二：回文字符串如"madam",若将其全部反转，则还是得到其本身"madam",在将两个字符串比较，若相等，则为回文
1，实现一个将字符串反转的函数
/*
*实现一个字符串的反转函数
*/
privateStringreverse(Stringstr){
StringstrResult="";
for(inti=str.length()-1;i>=0;i--){
strResult+=str.charAt(i);
}
returnstrResult;
}
2，对于目标字符串s，首先将其反转temp=reverse(s)，然后在判断temp.equals(s)
/*
*将字符串倒置，再与原字符串进行比较，若相等，则为回文，否则不是
*算法时间复杂度为O(n)
*/
publicbooleanisPalindrome2(Strings){
Stringtemp=reverse(s);
if(s.equals(temp))
returntrue;
else
returnfalse;
}
二：如何求一个给定字符串的最大回文字符串
例如，给定字符串StringT="google",如何求其最长的回文子字符串"goog"
1，最简单直接的想法就是：找出字符串的所有子串，然后判断每一个子串是否是回文，并记录，比较求出最大长度的回文，*算法时间复杂度为O(n^3)
/*
*4,求最长回文子串
*问题描述：给定一个字符串求出其所有子串中最长的回文子串，例如google字符串，最长子串为goog
*分析：
*1，最简单直接的想法就是：找出字符串的所有子串，然后判断每一个子串是否是回文，并记录，比较求出最大长度的回文
*算法时间复杂度为O(n^3)
*/
publicStringlongestPalindrome1(Strings){
Stringresult=null;
StringtempString="";
//定义最长回文子串的长度
intmax=0;
//遍历字符串中的所有元素
for(inti=0;i<s.length();i++){
//数组下标指针j从字符串后面开始往前遍历
for(intj=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);
}
}
}
returnresult;
}
2，第二种思路就是对于字符串中的每一个字符T[i]，判断
以T[i]，T[i+1]为中心的偶数长度子字符串是回文
T[i]为中心的奇数长度子字符串是否是回文
publicStringlongestPalindrome2(StringT){
Stringresult=null;
//存放最大回文字符串的长度
intmax=0;
//遍历每一个字符，以每一个字符为中心判断奇偶扩展子串
for(inti=0;i<T.length();i++){
//定义两个数组下标指针，以i，i+1为中心的偶子序列
intpStart=i;
intpEnd=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);
}
}
returnresult;
}