对于长度为n的一个字符串A（仅包含数字，大小写英文字母），请设计一个高效算法，计算其中最长回文子串的长度。
数据范围： 
要求：空间复杂度 )
，时间复杂度 )
进阶: 空间复杂度 )
，时间复杂度
[编程题]最长回文子串
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param A string字符串
* @return int整型
*/
public int getLongestPalindrome (String A) {
// write code here
int n = A.length();
int res = 1;
for (int i = 0; i < n; i++) {
int left = i;
int right = i;
while (left >= 0 && right < n) {
if (A.charAt(left) == A.charAt(right)) {
res = Math.max(right - left + 1, res);
left--;
right++;
}else{
break;
}
}
left = i;
right = i + 1;
while (left >= 0 && right < n) {
if (A.charAt(left) == A.charAt(right)) {
res = Math.max(right - left + 1, res);
left--;
right++;
}else{
break;
}
}
}
return res;
}
}
发表于 2025-10-19 12:29:27
回复(0)
public int getLongestPalindrome(String A) {
char[] chars = A.toCharArray();
int l = 1;
for (int i = 0; i < chars.length; i++) {
for (int j = i; j < chars.length; j++) {
if (chars[i] == chars[j]) {
int m = Compare(chars, i, j);
if (l < m) {
l = m;
}
}
}
}
return l;
}
public int Compare(char[] chars1, Integer i, Integer j) {
int n = j - i + 1;
if (n != 1) {
char[] chars2 = new char[n];
System.arraycopy(chars1, i, chars2, 0, n);
for (int o = 0; o < n; o++) {
if (chars2[o] != chars2[n - o - 1]) {
return 1;
}
}
return n;
} else {
return 1;
}
}
发表于 2025-04-02 13:56:22
回复(0)
方法一：动态规划预处理
该方法思路为。如果字串A[i..j]（左闭右闭）为回文串，那么有前提条件：A[(i+1)..(j-1)]为回文串，并且A[i] == A[j]。
时间复杂度：
空间复杂度：
import java.util.*;
public class Solution {
public int getLongestPalindrome (String A) {
int n = A.length();
if (A == null || n < 1) return 0;
boolean[][] dp = new boolean[n][n];
for (int i = 0; i < n; i++) Arrays.fill(dp[i], true);
int maxLen = 1;
for (int i = n-1; i >= 0; i--) {
for (int j = i+1; j < n; j++) {
dp[i][j] = dp[i+1][j-1] & (A.charAt(i) == A.charAt(j));
if (dp[i][j]) {
int len = j - i + 1;
maxLen = len > maxLen ? len : maxLen;
}
}
}
return maxLen;
}
} 方法二：枚举回文串中心位置
我们可以尝试枚举所有回文串的“中心位置”，并向两边进行拓展，直到无法拓展；此时比较回文串长度与已知最大长度。
时间复杂度：
空间复杂度:
import java.util.*;
public class Solution {
public int getLongestPalindrome (String A) {
if (A == null || A.length() < 1) return 0;
int maxLen = 0;
for (int i = 0; i < A.length(); i++) {
int len1 = expandAroundCenter(A, i, i);
int len2 = expandAroundCenter(A, i, i+1);
int len = Math.max(len1, len2);
maxLen = len > maxLen ? len : maxLen;
}
return maxLen;
}
private int expandAroundCenter(String A, int left, int right) {
while (left >= 0 && right < A.length() && A.charAt(left) == A.charAt(right)) {
left -= 1;
right += 1;
}
return right - left - 1;
}
}方法三：Manacher 算法
该算法可以达到时间复杂度，空间复杂度
的进阶要求，但比较复杂。
发表于 2025-03-03 15:04:30
回复(0)
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param A string字符串
* @return int整型
*/
public int getLongestPalindrome (String A) {
if (null==A||"".equals(A)) {
return 0;
} else if (A.length() == 1) {
return 1;
} else {
int length = 0;
Set<Character> charSet = new HashSet<Character>();
for (int i = 0; i < A.length(); i++) {
char c = A.charAt(i);
if (charSet.contains(c)) {
String temp = A.substring(A.indexOf(c), A.lastIndexOf(c) + 1);
length = Math.max(length, temp.length());
} else {
charSet.add(A.charAt(i));
}
}
System.out.println("length:" + length);
return length;
}
}
发表于 2025-02-26 18:39:48
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param A string字符串
* @return int整型
*/
public int getLongestPalindrome (String A) {
// write code here
// 填充字符串：123 -> #1#2#3#
// 注意，两边也要有#，这样直接除以2就能返回结果，否则还要分类讨论
StringBuilder sb = new StringBuilder();
for (int i = 0; i < A.length(); i++) {
sb.append('#');
sb.append(A.charAt(i));
}
sb.append('#');
String newS = sb.toString();
// 统计最长回文子串长度
// 基础写法 - 空间复杂度O(1)，时间复杂度O(N2)；
/*
int max = 0;
for (int i = 0; i < newS.length(); i++) {
int l = i;
int r = i;
int len = 0;
while (l >= 0 && r < newS.length() && newS.charAt(l) == newS.charAt(r)) {
if (newS.charAt(l) != '#') {
if (l == r) {
len++;
} else if (l != r && newS.charAt(l) != '#') {
len += 2;
}
}
l--;
r++;
}
if (len > max) {
max = len;
}
}
*/
// Manacher算法：空间复杂度O(N)，时间复杂度O(N)
// 设置一个长度为n的数组：表示以当前元素为中心的回文半径；
int[] lens = new int[newS.length()];
// 设置两个全局的变量：当前最大回文字串的右边界与中心点
// 初始化成-1，表示第一个元素就要外扩
int c = -1;
int b = -1;
int max = 0;
for (int i = 0; i < newS.length(); i++) {
if (i > b) {
// 1.当前元素超出了当前最大回文子串的右边界
// 直接双指针暴力扩
int left = i;
int right = i;
int len = 0;
while (left >= 0 && right < newS.length() && newS.charAt(left) == newS.charAt(right)) {
if (left == right) {
len++;
} else if (left != right) {
len += 2;
}
left--;
right++;
}
if (len > max) {
// 若当前回文子串突破了最大值，则更新c和b
max = len;
c = i;
b = right - 1;
}
// 无论如何，将当前i位置回文子串长度计入lens数组中对应i位置
lens[i] = right - 1 - i;
} else {
// 2.当前元素没有超过当前最大回文子串的右边界
// 必然能找到i相对于c的对称元素iSym，观察iSym的回文子串情况，进行分类讨论
int iSym = c * 2 - i;
int iSymR = lens[iSym];
int bSym = c * 2 - b;
if ((iSym - iSymR) > bSym) {
// 2.1 iSym的回文区域完全包含在bSym...c...b内
// 说明i位置的元素回文子串必然没有突破b的限制，因此不必进行统计，直接沿用iSym的半径和直径，且不必更新c和b；
lens[i] = lens[iSym];
} else if ((iSym - iSymR) < bSym) {
// 2.2 iSym的回文区域超出了bSym...c...b范围
// 说明iSym的回文超出bSym的部分必然没有对应在b处，要不然bSym和b的范围还会再此基础上再扩大，与当前确定的bSym和b范围相冲突，因此不必进行统计，i位置的回文半径就是i到b之间的部分，且不必更新c和b；
lens[i] = b - i;
} else {
// 2.3 i’的回文区域正好达到了bSym之上：
// 说明i到b的部分必然是i位置元素的回文，这部分不必验证，直接验证外面的元素就好，再根据验证的情况决定是否更新c和b：
int right = b + 1;
int left = i * 2 - right;
int len = (b - i) * 2 + 1;
while (left >= 0 && right < newS.length() && newS.charAt(left) == newS.charAt(right)) {
if (left == right) {
len++;
} else if (left != right) {
len += 2;
}
left--;
right++;
}
if (len > max) {
// 若当前回文子串突破了最大值，则更新c和b
max = len;
c = i;
b = right - 1;
}
// 无论如何，将当前i位置回文子串长度计入lens数组中对应i位置
lens[i] = right - 1 - i;
}
}
}
// 记得除以2排除#字符
return max / 2;
}
}
发表于 2024-11-14 19:34:36
回复(0)
public int getLongestPalindrome (String A) {
// write code here
int maxLen=0;
for(int i=0;i<A.length();i++){
int p1=i ,p2=i;
while(p2+1<A.length() && A.charAt(p2)==A.charAt(p2+1)){
p2++;
}
i=p2;
while(p1-1>=0 && p2+1<A.length() && A.charAt(p1-1)==A.charAt(p2+1)){
p1--;
p2++;
}
maxLen=Math.max(maxLen ,p2-p1+1);
}
return maxLen;
}
发表于 2024-09-22 15:36:22
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param A string字符串
* @return int整型
*/
public int getLongestPalindrome (String A) {
// write code here
if (A == null || A.isEmpty()) {
return 0;
}
int len = A.length();
int max = 1;
for (int i = 0; i < len; i++) {
StringBuilder str = new StringBuilder(String.valueOf(A.charAt(i)));
for (int j = i + 1; j < len; j++) {
StringBuilder append = str.append(A.charAt(j));
StringBuilder reverse = new StringBuilder(append);
reverse.reverse();
if (append.toString().contentEquals(reverse)) {
if (append.length() > max) {
max = append.length();
}
}
}
}
return max;
}
}
发表于 2024-07-04 16:26:41
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param A string字符串
* @return int整型
*/
public int getLongestPalindrome (String A) {
// write code here
int n = A.length();
int max = 1;
for (int i = 0; i < n; i++) {
for (int j = n - 1; j > i ; j--) {
String sub = A.substring(i, j + 1);
StringBuffer a = new StringBuffer(sub).reverse();
if (sub.equals(a.toString())) {
max = Math.max(max, a.length());
}
}
}
return max;
}
}
发表于 2024-06-18 10:06:55
回复(0)
public int getLongestPalindrome(String s) {
StringBuilder sb = new StringBuilder(s);
int n = sb.length();
boolean[][] dp = new boolean[n][n];
int res = 1;
for (int i = 0; i < n; i++) {
dp[i][i] = true;
}
for (int j = 1; j < n; j++) {
for (int i = j - 1; i >= 0; i--) {
if (j - i <= 2 && sb.charAt(i) == sb.charAt(j)) {
dp[i][j] = true;
res = Math.max(res, j - i + 1);
} else if (sb.charAt(i) == sb.charAt(j)) {
dp[i][j] = dp[i + 1][j - 1];
if (dp[i][j]) {
res = Math.max(res, j - i + 1);
}
}
}
}
return res;
}
发表于 2024-05-08 15:31:03
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* @param A string字符串
* @return int整型
*/
public int getLongestPalindrome (String A) {
// write code here
if (A.length() == 1) return 1;
if (A.isEmpty()) return 0;
int maxCount = 0;
for (int i = 0; i < A.length(); i++) {
int j = 0;
while (j <= i) {
String temp = A.substring(j, A.length() - i + j);
String newTemp = String.valueOf(new StringBuilder(temp).reverse());
if (temp.equals(newTemp) && temp.length() > maxCount) {
return temp.length();
}
j++;
}
}
return 0;
}
}
发表于 2024-01-10 09:49:27
回复(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 line = in.nextLine();
int count = getMaxStr(line, 0, line.length() - 1);
System.out.println(count);
// }
}
public static int getMaxStr(String str, int l, int r ) {
if (l == r) {
return 1;
}
if (l == r - 1) {
return str.charAt(l) == str.charAt(r - 1) ? 2 : 1;
}
//决定的有4个方式
int p1 = getMaxStr(str, l + 1, r);
int p2 = getMaxStr(str, l, r - 1);
int p3 = getMaxStr(str, l + 1, r - 1);
int p4 = str.charAt(l) == str.charAt(r) ? 2 : 0 ;
if (p4 != 0) {
p4 = p4 + getMaxStr(str, l + 1, r - 1);
}
return Math.max(p1, Math.max(p2, Math.max(p3, p4)));
}
}
编辑于 2024-01-06 19:48:45
回复(1)
import java.util.*;
public class Solution {
public int getLongestPalindrome(String A) {
int n = A.length();
if (n < 2) {
return n;
}
// 最大长度
int res = 0;
// 每个字符都可以尝试作为中心点
for (int i = 1; i < n + 1; i++) {
// 两种情况：可能是类似 aba 的字符串，也可能是类似 abba 的情况
// 只需要分别计算出以一个和两个字符作为中心点的子串，取出较大的长度即可
for(int j = 0; j< n - i + 1 ; j++) {
String subStr = A.substring(j,j + i);
//System.out.println(subStr);
int len = helper(subStr);
// 更新最大长度
res = Math.max(res, len);
}
}
return res;
}
public int helper(String subStr) {
char[] arr = subStr.toCharArray();
StringBuffer bf = new StringBuffer(subStr);
String reverseStr = bf.reverse().toString();
return subStr.equals(reverseStr) ? subStr.length():1;
}
}
编辑于 2024-01-04 00:50:05
回复(0)
大佬们能不能看看我的有什么问题，倒数第二个用例不通过
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param A string字符串
* @return int整型
*/
public int getLongestPalindrome (String A) {
// write code here
String B = new StringBuffer(A).reverse().toString();
int[][] dp = new int[A.length() + 1][A.length() + 1];
for (int i = 1; i <= A.length(); i++)
for (int j = 1; j <= A.length(); j++){
if (A.charAt(i - 1) == B.charAt(j - 1))
dp[i][j] = dp[i - 1][j - 1] + 1;
}
int[] len = new int[dp.length];
for (int i = 0; i < dp.length; i++) {
int max = Arrays.stream(dp[i]).max().getAsInt();
len[i] = max;
}
return Arrays.stream(len).max().getAsInt();
}
}
发表于 2023-12-03 23:23:38
回复(0)
import java.util.*;
public class Solution {
public int getLongestPalindrome (String A) {
// write code here
int maxlen = 1;
int n = A.length();
boolean[][] dp = new boolean[n][n];
for(int right = 1; right < n; right++){
for(int left = 0; left <= right; left++){
//两端字符不相同，必定不是回文，直接略过
if(A.charAt(left) != A.charAt(right))
continue;
//当窗口内只有1个字符或两个字符时候，一定是回文。如："a", "aa", 其实这里相当于起始条件。
if(right-left<=1){
dp[left][right] = true;
}else{
dp[left][right] = dp[left+1][right-1];
}
if(dp[left][right] && right-left+1>maxlen){
maxlen = right-left+1;
}
}
}
return maxlen;
}
}
发表于 2023-08-31 13:02:43
回复(0)
这个问题可以转化为求两个字符串的公共最长字串问题。将字符串反转，反转后的回文串和反转前的回文串一定相等。就比求两个字符串的最长公共子串多一个条件就行。回文串反转后的位置和反转前的位置是有相确定性的。反转后的回文串的第一个字符的位置等于字符串的长度减去反转前的回文串的最后一个字符的位置，这就是他们的相关性。
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param A string字符串
* @return int整型
*/
public int getLongestPalindrome (String A) {
// write code here
String reverse = new StringBuilder(A).reverse().toString();
int result = 0;
for (int i = 0; i < A.length(); i++) {
if (result > A.length() - i) {
break;
}
for (int j = i + 1 + result; j <= A.length(); j++) {
String substring = A.substring(i, j);
if (reverse.contains(substring)) {
// 求出公共子串
if (reverse.substring(reverse.length() - j,
reverse.length() - i).equals(substring)) {
// 如果位置满足回文串的相关性，那么就是回文串没错了
result = substring.length();
}
} else {
break;
}
}
}
return result;
}
}
发表于 2023-08-20 20:13:53
回复(0)
从中间向两边，这样时间复杂度应该会低一些，不知道是多少
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param A string字符串
* @return int整型
*/
public int getLongestPalindrome (String A) {
// write code here
int length = A.length();
int count = length > 0 ? 1 : 0;
for (int i = 0 ; i < length - 1; i++) {
char c = A.charAt(i);
int d = find(i, -1, length, A);
if (count < d) {
count = d;
}
if (c == A.charAt(i + 1)) {
d = find(i, i + 1, length, A);
if (count < d) {
count = d;
}
}
}
return count;
}
public int find(int i, int y, int length, String A) {
int count = 0;
int j = i - 1;
int k = y == -1 ? i + 1 : y + 1;
if (j < 0 || k >= length) {
return y - i + 1;
}
for (; j >= 0 && k <= length - 1; j--, k++) {
char c1 = A.charAt(j);
char c2 = A.charAt(k);
if (c1 != c2) break;
}
if (count < k - j - 1) {
count = k - j - 1;
}
return count;
}
}
发表于 2023-08-19 17:56:33
回复(0)
public int getLongestPalindrome (String A) {
if(A==null){
return 0;
}
if(A.length()<2){
return A.length();
}
int ans=1;
for(int i=0;i<A.length();i++){
for(int j=i+1;j<A.length();j++){
String str=A.substring(i,j+1);
if(str.equals(new StringBuilder(str).reverse().toString())){
ans=Math.max(ans,str.length());
}
}
}
return ans;
}
发表于 2023-07-10 23:24:27
回复(0)
可能我只会简单粗暴的方法
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param A string字符串
* @return int整型
*/
public int getLongestPalindrome (String A) {
if (A.length() <= 1) {
return A.length();
}
int max = 1;
for (int i = 0; i < A.length(); i++) {
for (int j = i + 1; j < A.length(); j++) {
String substring = A.substring(i, j + 1);
if (substring.equals(new StringBuilder(substring).reverse().toString())) {
max = Math.max(max, substring.length());
}
}
}
return max;
}
}
发表于 2023-05-18 08:25:00
回复(0)
问题信息
通过挑战的用户
查看代码-
2023-03-12 11:49:39 -
2023-03-11 21:34:19
-
2023-03-09 16:16:00
-
2023-03-08 15:23:26 -
2023-03-08 15:07:36
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
