对于长度为n的一个字符串A（仅包含数字，大小写英文字母），请设计一个高效算法，计算其中最长回文子串的长度。
数据范围： 
要求：空间复杂度 )
，时间复杂度 )
进阶: 空间复杂度 )
，时间复杂度
[编程题]最长回文子串
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
回复(0)
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)
import java.util.*;
//很笨 public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param A string字符串
* @return int整型
*/
public int getLongestPalindrome (String A) {
// write code here
int n = 0;
if (A.length() == 0) return 0;
if (A.length() == 1) return 1;
StringBuffer S = new StringBuffer(A);
for (int i = 0; i <= A.length(); i++) {
for (int j = i + 1; j <= A.length() ; j++) {
String B = A.substring(i, j);
StringBuffer C = new StringBuffer(B);
String D = C.reverse().toString();
if (B.equals(D)) {
n = Math.max(n, B.length());
}
}
}
return n;
}
}
发表于 2023-03-28 11:18:05
回复(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 19:46:47
回复(0)
import java.util.*;
//投机取巧的方法
public class Solution {
public int getLongestPalindrome (String A) {
int[] arr = new int[A.length()];
int max = 1;
for (int i = 0; i < A.length(); i++)
for (int j = i + 1; j < A.length(); j++) {
String temp = new StringBuffer(A.substring(i, j + 1)).toString();
String temp2 = new StringBuffer(temp).reverse().toString();
if (temp.equals(temp2)) {
max = Math.max(max, j - i + 1);
}
}
return max;
}
}
发表于 2023-03-17 20:28:06
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param A string字符串
* @return int整型
*/
public int getLongestPalindrome (String A) {
// write code here ababc
int ans = 0;
for (int i = 0; i < A.length(); i++) {
for (int j = i + 1; j <= A.length(); j++) {
if (isPalindrome(A.substring(i, j))) {
ans = Math.max(ans, j - i);
}
}
}
return ans;
}
private boolean isPalindrome(String s) {
return new StringBuilder(s).reverse().toString().equals(s);
}
} O(n3)
发表于 2023-03-03 18:12:52
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param A string字符串
* @return int整型
*/
static int maxLength = 0;
public int getLongestPalindrome (String A) {
// write code here
for(int i = 0;i<A.length();i++){
updateMax(A,i,i,A.length());
updateMax(A,i,i+1,A.length());
}
return maxLength;
}
public static void updateMax(String A,int i,int j ,int n){
while(i>=0 && j<n && A.charAt(i) == A.charAt(j)){
if(j-i+1 > maxLength){
maxLength = j-i+1;
}
i--;
j++;
}
}
}
发表于 2023-03-02 14:40:23
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param A string字符串
* @return int整型
*/
public int getLongestPalindrome (String A) {
// write code here
int res = 1;
for (int i = 0; i < A.length(); i++) {
for (int j = 1; j < A.length(); j++) {
if (j > i) {
String substring = A.substring(i, j + 1);
if (substring.equals(new StringBuilder().append(
substring).reverse().toString())) {
res = Math.max(res, substring.length());
}
}
}
}
return res;
}
}
发表于 2022-11-30 10:41:07
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param A string字符串
* @return int整型
*/
public int getLongestPalindrome (String A) {
// 动态规划 空间复杂度O(n^2) 时间复杂度O(n^2)
int len = A.length();
if(len == 1) return 1;
// 1.初始化dp数组，
// dp[j][i]的含义为: 从 i - j的子串是否为回文子串
boolean[][] dp = new boolean[len][len];
// 2.初始化dp数组元素，
// 这一步初始化，意思为 从i - i的 位置的dp单元格 为true， 也就是单个字符都可以是回文子串
for (int i = 0; i < len; i++) dp[i][i] = true;
// 初始化回文子串最大长度为1
int maxLen = 1;
// 3.开始循环子串, 整个dp数组只用到了斜对角的一半，另一半没用
// 外层循环j 表示右边界， 从i ~ j
for (int j = 1; j < len; j++) {
// 内层循环i 表示左边界
for (int i = 0; i < j; i++) { // i每次从0开始，递增到j - 1的位置，依次和j比对
// 如果j索引字符 == i索引字符时
if(A.charAt(j) == A.charAt(i)){
// j - i == 1 表示i 和 j紧挨着，
// 那么不需要取 dp[j - 1][i + 1]的值，直接将dp[j][i] = true即可
if(j - i == 1) dp[j][i] = true;
// 否则，i 和 k 并不是挨着的，则需要判断i ~ j 之间的字符串是否是回文字符串，
// 只需要取出dp[j - 1][i + 1]位置的元素即可，它的结果就是当前由i - j的是否为回文子串
else dp[j][i] = dp[j - 1][i + 1];
// 判断结束后，如果dp[j][i] 依然为true，
// 那么就获取当前循环遍历到的回文子串长度 (j - i + 1 即为当前 从i到j的实际字符串长度，+1是因为下标从0开始)
// 与原有的maxLen 取最大值，重新赋值给maxLen
if(dp[j][i]) maxLen = Math.max(j - i + 1, maxLen);
}
}
}
/*for (boolean[] booleans : dp) {
System.out.println(Arrays.toString(booleans));
}*/
// 循环结束maxLen即为解
return maxLen;
}
/* 暴力解法: 枚举所有子串 时间复杂度O(n^3) 空间复杂度O(1)
public int getLongestPalindrome (String A) {
int len = A.length();
if(len == 1) return 1;
int max = 1;
int mid;
for (int i = 1; i < len; i++) {
// 内循环依次倒序遍历，
for (int j = i - 1; j >= 0 ; j--) {
// 判断是否为回文结构
if(search(j, i, A)){
// 如果是，则 i - j + 1 得到真实数组元素数量
max = Math.max(i - j + 1, max);
}
}
}
return max;
}
public boolean search(int left, int right, String A){
while (left < right){
if(A.charAt(left) == A.charAt(right)){
left++;
right--;
}else{
return false;
}
}
return true;
}*/
}
发表于 2022-11-27 22:11:24
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param A string字符串
* @return int整型
*/
public int getLongestPalindrome (String A) {
// write code here
if (A == null || A.length() == 0) {
return 0;
}
if (A.length() < 2) {
return 1;
}
int max = 0;
for (int i = 0; i < A.length(); i++) {
// 中心扩散法
// 以当前点为中心向左右扩散
if (i > 0 && i + 1 < A.length()) {
max = Math.max(max, getTwoWay(A, i - 1, i + 1) + 1);
}
// 以当前点的左边点和当前点扩散
if (i > 0 && A.charAt(i - 1) == A.charAt(i)) {
max = Math.max(max, getTwoWay(A, i - 1, i));
}
// 以当前点和右边点扩散
if (i + 1 < A.length() && A.charAt(i + 1) == A.charAt(i)) {
max = Math.max(max, getTwoWay(A, i, i + 1));
}
}
return max == 0 ? 1 : max;
}
public int getTwoWay (String str, int left, int right) {
int count = 0;
while (left >= 0 && right < str.length()) {
if (str.charAt(left) != str.charAt(right)) {
break;
} else {
count++;
left--;
right++;
}
}
return count * 2;
}
}
发表于 2022-11-05 14:40:05
回复(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
相关试题
-
评论(174) 来自经典算法题精讲（四）-M...
-
评论(118) 来自经典算法题精讲（四）-M...
-
评论(93) 来自经典算法题精讲（四）-M...
-
评论(1)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
