给定一个仅包含小写字母的字符串，求它的最长回文子串的长度。
所谓回文串，指左右对称的字符串。
所谓子串，指一个字符串删掉其部分前缀和后缀（也可以不删）的字符串
数据范围：字符串长度
进阶：时间复杂度：%5C)
，空间复杂度：
[编程题]最长回文子串
import java.util.Scanner;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
int maxLen = 0;
for (int i = 0; i < line.length(); i++) {
for (int j = i + 1; j <= line.length(); j++) {
// 回文字符串 反转后与其自身相等
String sub = line.substring(i, j);
StringBuilder sb = new StringBuilder(sub);
if (sub.equals(sb.reverse().toString()) && sub.length() > maxLen) {
maxLen = sub.length();
}
}
}
System.out.println(maxLen);
}
}
发表于 2023-08-13 15:58:56
回复(0)
和HJ32 密码截取一模一样，直接粘过来
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 使用双指针法,从中心点到两边扩散,注意有两种星形式的回文子串
String str = in.nextLine();
// 定义左右指针
int l;
int r;
// 定义集合接收回文字符的长度
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < str.length() - 2; i++) {
// ABBA型
int len1 = 0;
if (str.charAt(i) == str.charAt(i + 1)) {
// 两边发散继续寻找
l = i;
r = i + 1;
do {
len1 += 2;
l--;
r++;
} while (r < str.length() && str.charAt(l) == str.charAt(r));
}
// ABA型 不是加2 初始值是1
int len2 = 1;
if (str.charAt(i) == str.charAt(i + 2)) {
// 两边发散继续寻找
l = i;
r = i + 2;
do {
len2 += 2;
l--;
r++;
//防止数组越界异常前置判断
} while (l >= 0 && r < str.length() && str.charAt(l) == str.charAt(r));
}
list.add(Math.max(len1, len2));
}
System.out.println(Collections.max(list));
}
}
发表于 2023-06-30 21:09:23
回复(1)
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
String str=in.nextLine();
int len=str.length();
if(len<1||len>350)
return;
int count1=0,count2=0;
int pos1=0,pos2=1;
for(int i=1;i<len-1;i++)
{
pos2=i;pos1=i-1;
if(str.charAt(i-1)==str.charAt((i)))
{
pos1=i-1;pos2=i;
}
else if(str.charAt(i-1)==str.charAt((i+1)))
{
pos1=i-1;pos2=i+1;
}
while(str.charAt(pos1)==str.charAt(pos2))
{
count2=pos2-pos1+1;
pos1--;pos2++;
if(pos1<0||pos2>=len)
break;
}
if(count2>count1)
count1=count2;
count2=0;
}
System.out.println(count1);
}
}
//瞎写
发表于 2023-06-28 22:45:51
回复(0)
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String a = in.nextLine();
int max = 0;
for (int i = 0; i < a.length(); i++) {
for (int j = i+1; j <= a.length(); j++) {
String sub = a.substring(i,j);
if (isPalindrome(sub) && sub.length() > max){
max = sub.length();
}
}
}
System.out.println(max);
}
private static boolean isPalindrome(String str){
StringBuilder sub = new StringBuilder(str).reverse();
if (str.equals(sub.toString())){
return true;
}
return false;
}
}
发表于 2023-06-07 14:30:46
回复(0)
回文长度
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String line = in.nextLine();
int num = 1; // 默认回文最小长度为1(单个字符)
for (int i = 0; i < line.length(); i++) {
// 回文长度为偶数
int k = Math.min(i + 1, line.length() - i - 1);
int idx = 0;
while (k > idx) {
if (line.charAt(i - idx) != line.charAt(i + 1 + idx)) {
break;
}
idx++;
}
num = Math.max(num, 2 * idx);
// 回文长度为奇数
k = Math.min(i, line.length() - i - 1);
idx = 0;
while (k > idx) {
if (line.charAt(i - 1 - idx) != line.charAt(i + 1 + idx)) {
break;
}
idx++;
}
num = Math.max(num, 2 * idx + 1);
}
System.out.println(num);
}
}
发表于 2023-05-14 18:29:39
回复(0)
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNext()) { // 注意 while 处理多个 case
String a = in.next();
TreeMap<Integer,String> treeMap = new TreeMap<Integer,String>();
for(int i=0;i<a.length();i++){
for(int j=a.length();j>i;j--){
StringBuffer bf = new StringBuffer();
String substr = a.substring(i,j);
bf.append(substr);
String reverse = bf.reverse().toString();
if(substr.endsWith(reverse)){
treeMap.put(substr.length(),substr);
}
}
}
System.out.println(treeMap.lastEntry().getKey());
}
}
发表于 2023-04-19 19:30:23
回复(0)
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static int[] p1=new int[400];
public static int[] p2=new int[400];
public static int[] p3=new int[400];
public static int[] dp=new int[400];
public static boolean check(int x,int y){
int a=p2[y]-p2[x-1]*p1[y-x+1];
int b=p3[x]-p3[y+1]*p1[y-x+1];
return a==b;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNext()) { // 注意 while 处理多个 case
Arrays.fill(p2,0);
Arrays.fill(p3,0);
Arrays.fill(dp,0);
String s=in.next();
int n=s.length(),ans=0;
p1[0]=1;
for(int i=1;i<=n;i++){
dp[i]=1;
p1[i]=p1[i-1]*27;
p2[i]=p2[i-1]*27+(s.charAt(i-1)-'a');
p3[n-i+1]=p3[n-i+2]*27+(s.charAt(n-i)-'a');
}
for(int i=1;i<=n;i++){
if(i-dp[i-1]>0&&check(i-dp[i-1],i)) dp[i]=Math.max(dp[i-1]+1,dp[i]);
if(i-1-dp[i-1]>0&&check(i-1-dp[i-1],i)) dp[i]=Math.max(dp[i-1]+2,dp[i]);
ans=Math.max(ans,dp[i]);
}
System.out.println(ans);
}
}
}
发表于 2023-04-09 20:10:54
回复(0)
/**
* ☆☆☆☆☆
* 最长回文子串
* 中心扩展 + 动态规划 + Manacher
*/
private static void longestPalindrome2() {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
String s = in.nextLine();
// 字符间隔及两边插入#，方便统一中心扩展方式的两种情况：中心在元素上和中心在元素间
StringBuilder sb = new StringBuilder("#");
for (int i = 0; i < s.length(); i++) {
sb.append(s.charAt(i)).append("#");
}
// 数组用于存插入#后，当前元素为中心的最大回文半径（自身算1）
// 最终的最大回文长度是该半径-1（该半径多出来的#，比另一边的原字符多一）
int[] arr = new int[sb.length()];
// 已知的所有回文串的最右边界+1
int maxPos = 0;
// 边界最右的回文串的中心
int index = 0;
for (int i = 0; i < sb.length(); i++) {
if (i < maxPos) {
// 此处是关键，i相对index的对称位置2*index-i，直接参与计算，避免重复计算
arr[i] = Math.min(arr[2 * index - i], maxPos - i);
} else {
arr[i] = 1;
}
// 在已有基础上继续扩展判断，越界判断，以及两边字符判断
while (i - arr[i] >= 0 && i + arr[i] < sb.length() && sb.charAt(i - arr[i]) == sb.charAt(i + arr[i])) {
arr[i]++;
}
// 更新maxpos和index
if (i + arr[i] > maxPos) {
maxPos = i + arr[i];
index = i;
}
}
int max = 0;
for (int i = 0; i < sb.length(); i++) {
max = Math.max(max, arr[i]);
}
// 最长回文串的长度
System.out.println(max - 1);
// 最长回文串
for (int i = 0; i < sb.length(); i++) {
if (max == arr[i]) {
String result = sb.substring(i - arr[i] + 1, i + arr[i]).replace("#", "");
System.out.println(result);
break;
}
}
}
}
发表于 2023-03-25 20:07:06
回复(0)
动态规划
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNext()) { // 注意 while 处理多个 case
String str = in.nextLine();
// dp[i][j]数组， 标记下标i-j是否为回文串，
// 1. 单个字符肯定是回文串， dp[i][i] == true
// 2. 如果i～j是回文子串，那么i+1～j-1肯定也是回文子串
String subStr = getMaxLongStr(str);
System.out.println(subStr.length());
}
}
private static String getMaxLongStr(String str) {
int begin = 0;
int maxLen = 1;
int len = str.length();
char[] arr = str.toCharArray();
// 定义dp数组
// 单个字符都是回文
boolean[][] dp = new boolean[len][len];
for (int i = 0; i < len; i++) {
dp[i][i] = true;
}
// dp[i][j] 参考的是 dp[i+1][j-1]
// 边界条件： (j-1) - (i+1) + 1 < 2,则不需要参考
// 整理： j - i < 3
for (int j = 1; j < len; j++) {
for (int i = 0; i < j; i ++) {
if (arr[i] != arr[j]) {
dp[i][j] = false;
} else {
if (j - i < 3) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i+1][j-1];
}
}
// 更新最大子串
if (dp[i][j] && j - i + 1 > maxLen) {
begin = i;
maxLen = j - i + 1;
}
}
}
return str.substring(begin, begin+maxLen);
}
}
发表于 2023-03-16 13:53:09
回复(0)
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String s1 = in.nextLine();
in.close();
int size = s1.length();
int res = 1;
for (int k = 0; k < size; k++) {
res = Math.max(res, centreExtend(s1, k, k, size));
}
for (int k = 0; k < size-1; k++) {
if (s1.charAt(k) == s1.charAt(k+1)) {
res = Math.max(res, centreExtend(s1, k, k+1, size));
}
}
System.out.println(res);
}
private static int centreExtend(String s1, int i, int j, int size) {
while (i-1 >= 0 && j+1 < size && s1.charAt(i-1) == s1.charAt(j+1)) {
i--;
j++;
}
return j - i + 1;
}
}
发表于 2023-03-02 13:26:50
回复(0)
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
//中心扩散法，
String str=in.nextLine();
int sum=0;
for(int i=0;i<str.length();i++){
//两种类型的串 ABA。ABBA
int num=GetCount(str,i,i);//奇数串
int num2=GetCount(str,i,i+1);//偶数串
int max=Math.max(num,num2);
if(sum<max) sum=max;
}
System.out.print(sum);
}
//中心扩散法，比较l和r位置的字符是否相同，相同则
private static int GetCount(String str,int l,int r) {
int count=0;
while(l>=0&&r<str.length()&&str.charAt(l)==str.charAt(r)){
l--;
r++;
count=r-l-1;
}
return count;
}
}
发表于 2023-02-03 16:19:29
回复(0)
想到了一个复杂点但效率高的写法：
就遍历字符串每个字符，然后从这开始通过判断这个字符左右是否对称，对称则说明是回文字符串，且是最短的回文字符串。
如果对称则左右分别向外扩1，再比较两个扩出去的字符。
不同说明左右单个字符不一样，此时就不是回文字符串了，相同则重复。
（注意边界情况）
分两种情况：一种是"aa"。一种是“aba”;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String str = in.nextLine();
char[] ch = str.toCharArray();
int lengthMax = 0;
for (int i = 0; i < str.length() - 1; i++) {
// 找到一个长度为2的回文子串
if (ch[i] == ch[i + 1]) {
int temp = 1;
// 该次遍历最长回文串
String strMax;
// 同时向该回文子串两边向外递增直至不对称
while ((i - temp) >= 0 && (i + 1 + temp) < ch.length) {
if (ch[i - temp] == ch[i + 1 + temp]) {
temp++;
} else {
break;
}
}
// 截取temp-1时的情况，此时即当前i时最大回文字符串
strMax = str.substring(i - temp + 1, i + 1 + temp);
if (lengthMax < strMax.length()) {
lengthMax = strMax.length();
}
}
// 找到一个长度为3的回文子串
if (i - 1 >= 0 && ch[i - 1] == ch[i + 1]) {
int temp = 1;
// 该次遍历最长回文串
String strMax;
// 同时向该回文子串两边向外递增直至不对称
while ((i - 1 - temp) >= 0 && (i + 1 + temp) < ch.length) {
if (ch[i - 1 - temp] == ch[i + 1 + temp]) {
temp++;
} else {
// 外扩后左右字符不同时
break;
}
}
// 截取temp-1时的情况，此时即当前i时最大回文字符串
strMax = str.substring(i - 1 - temp + 1, i + 1 + temp);
// 找所有最大情况
if (lengthMax < strMax.length()) {
lengthMax = strMax.length();
}
}
}
System.out.println(lengthMax);
}
}
发表于 2022-09-20 14:07:03
回复(0)
求出所有的子字符串，再利用子字符串比较，简单易懂
import java.io.BufferedReader;
import java.io.IOException;
import java.util.*;
import java.util.ArrayList;
public class Main {
public static void main(String[] args) throws IOException {
Scanner scan = new Scanner(System.in);
String str = scan.next();
if(str.length()==0){
System.out.print(0);
return;
}
StringBuilder stb = new StringBuilder(str);
String temp = stb.reverse().toString();
int max = 1;
int len = str.length();
ArrayList <String> arr = new ArrayList<String>();
for(int i=0;i<len-1;i++){
for(int j=i;j<=len;j++){
arr.add(str.substring(i,j));
}
}
for(int i=0;i<arr.size();i++){
String ss =arr.get(i);
if(ss.equals(new StringBuilder(ss).reverse().toString())){
if(max< ss.length())
max = ss.length();
}
}
System.out.print(max);
}
}
发表于 2022-08-29 16:51:14
回复(2)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
int n = s.length();
int[][] dp = new int[n][n];
int res = 1;
for(int i = n - 1;i >= 0;i--){
dp[i][i] = 1;
for(int j = i + 1;j < n;j++){
if(s.charAt(i) == s.charAt(j)){
if(j - i < 3){
dp[i][j] = j - i + 1;
}else{
dp[i][j] = dp[i + 1][j - 1] > 0 ? j - i + 1 : 0;
}
if(dp[i][j] > 0 && j - i + 1 > res) res = j - i + 1;
}
}
}
System.out.println(res);
}
}
发表于 2022-08-10 15:14:23
回复(0)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str;
while((str=br.readLine())!=null){
int max=0;
for(int i=0;i<str.length()-1;i++){
for(int j=str.length()-1;j>i;j--){
if(max>j-i+1){
break;
}
String nstr=str.substring(i,j+1);
boolean flag=true;
for(int a=0;a<=nstr.length()/2;a++){
if(nstr.charAt(a)!=nstr.charAt(nstr.length()-1-a)){
flag=false;
break;
}
}
if(flag&&nstr.length()>max){
max=nstr.length();
}
}
if(max>str.length()-i){
break;
}
}
System.out.println(max);
}
}
}
发表于 2022-07-31 13:25:49
回复(0)
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String nextLine = scanner.nextLine();
int length = nextLine.length();
int maxLength = 0;
for (int i = 0; i < length; i++) {
for (int j = length; j > i; j--) {
String substring = nextLine.substring(i, j);
if (isHuiwen(substring)) {
maxLength = Math.max(maxLength, j - i);
}
}
}
System.out.println(maxLength);
}
private static boolean isHuiwen(String substring) {
StringBuffer buffer = new StringBuffer(substring).reverse();
boolean equals = substring.equals(buffer.toString());
return equals;
}
}
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String nextLine = scanner.nextLine();
int length = nextLine.length();
int maxLength = 0;
for (int i = 0; i < length; i++) {
for (int j = length; j > i; j--) {
String substring = nextLine.substring(i, j);
if (isHuiwen(substring)) {
maxLength = Math.max(maxLength, j - i);
}
}
}
System.out.println(maxLength);
}
private static boolean isHuiwen(String substring) {
StringBuffer buffer = new StringBuffer(substring).reverse();
boolean equals = substring.equals(buffer.toString());
return equals;
}
}
发表于 2022-06-15 17:13:09
回复(0)
问题信息
难度：
64条回答
2328收藏
31415浏览
通过挑战的用户
查看代码-
2023-03-14 15:57:42 -
2023-02-25 16:47:53 -
2023-01-07 14:54:36 -
2022-10-17 21:05:10
-
2022-09-16 18:56:10
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
