Java实现查找当前字符串最大回文串代码分享
作者:hebedich 发布时间:2023-07-30 04:05:02
标签: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="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;
}
0
投稿
猜你喜欢
- yaml语法注解配置文件两种形式application.properties和.yaml第一种语法 key=value第二种key:空格va
- 前言在java Thread类中,我们会看到interrupt()、interrupted()及isInterrupted(),在大多数情况
- fopen(打开文件)相关函数 open,fclose表头文件 #include<stdio.h>定义函数 FILE * fop
- 前言gps定位服务的学习是这段时间gps课程的学习内容,之前老师一直在将概念,今天终于是实践课(其实就是给了一个案例,让自己照着敲).不过在
- Android 无障碍的全局悬浮窗可以在屏幕上添加 UI 供用户进行快捷操作,可以展示在所有应用程序之上长期展示。另一方面,在一些自动化场景
- 利用Android的ApiDemos的Rotate3dAnimation实现了个图片3D旋转的动画,围绕Y轴进行旋转,还可以实现Z轴的缩放。
- 本文实例为大家分享了C#超市收银系统设计的具体代码,供大家参考,具体内容如下1.登录界面代码如下:using System;using Sy
- 我们知道在编程时许多操作(如更新UI)需要在主线程中完成,而且,耗时操作(如网络连接)需要放在子线程中,否则会引起ANR。所以我们常使用Ha
- 上篇介绍了几种图表的公共组件X、Y轴、背景Board的绘制。这章节介绍柱状图表的绘制,相对其它图表而言简单一些,这里主要介绍图表主体的绘制,
- Android5.0之后提供了JobService和JobScheduler,用于在稍后的某个时间点或者当满足某个特定的条件时执行一个任务
- 首先给出一段代码:public class AslistMethod { public static void main(String[]
- 在观察者模式中有2个要素:一个是被观察对象,另一个是观察者。但被观察对象的状态发生改变会通知观察者。举例:把订阅报纸的人看作是观察者,把报纸
- 光流的概念是由一个叫Gibson的哥们在1950年提出来的。它描述是空间运动物体在观察成像平面上的像素运动的瞬时速度,利用图像序列中像素在时
- SharedPreferences介绍:SharedPreferences是Android平台上一个轻量级的存储类,主要是保存一些常用的配置
- 效果展示人脸支付效果视频密码框输入支付效果视频因为密码支付时会调起系统安全键盘,开启自动保护功能,防止泄露,会导致输入密码时录屏黑屏,故使用
- Android之文件数据存储一、文件保存数据介绍Activity提供了openFileOutput()方法可以用于把数据输出到文件中,具体的
- 一、前言在Spring中,事务有两种实现方式:编程式事务管理: 编程式事务管理使用TransactionTemplate可实现更细
- 对接前端后效果展示如图:1、CPU相关信息实体类/** * CPU相关信息 * * @author csp */public class
- 本文介绍了Spring Boot Admin监控服务上下线邮件通知,分享给大家,具体如下:微服务架构下,服务的数量少则几十,多则上百,对服务
- 仅供学习交流,禁止商业用途。如侵害利益,联系必删!前言最近一位小伙伴钟爱二次元文化,于是找到半次元这个app,但是很快他就遇到了问题。一、案