首页 > 试题广场 >

回文字符串

[编程题]回文字符串
  • 热度指数：9429 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
最大回文子串是被研究得比较多的一个经典问题。最近月神想到了一个变种，对于一个字符串，如果不要求子串连续，那么一个字符串的最大回文子串的最大长度是多少呢。

数据范围：字符串长度满足 ，字符串中仅包含 0~9 和大小写字母

输入描述:
每个测试用例输入一行字符串（由数字0-9，字母a-z、A-Z构成），字条串长度大于0且不大于1000.


输出描述:
输出该字符串的最长回文子串的长度。（不要求输出最长回文串，并且子串不要求连续）
示例1

输入

adbca

输出

3

说明

因为在本题中，不要求回文子串连续，故最长回文子串为aba(或ada、aca)

备注:
因为不要求子串连续，所以字符串abc的子串有a、b、c、ab、ac、bc、abc7个
算法知识视频讲解
开通博客
头像 牛客题解官
发表于 2020-06-04 14:51:22
精华题解 题目难度：二星 考察点：动态规划 方法1：暴力、二进制枚举 1. 分析 我们分析一下题意，对于每个输入的字符串s，它的子串(包括不连续的子串)有2^n个，其中n为字符串s的长度，那么我们就可以枚举这2^n个子串，判断当前枚举到子串是不是回文字符串，如果是回文字符串的话，就记录答案，并取 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 洁白
发表于 2019-09-18 11:15:20
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); S 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 laglangyue
发表于 2020-05-23 22:59:55
package org.niuke.solution23; import java.util.Scanner; public class Main { public static void main(String[] args){ Scanner scanner = n 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 流浪~~
发表于 2021-11-07 21:42:24
就是这一小块，难了半天，最后看题解才发现递推公式搞错了。。。 we[i][j] = Math.max(we[i+1][j],we[i][j-1]); import java.util.*; public class Main{ public static void main(String[] 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 小熊_008
发表于 2021-08-19 10:20:58
dp[i][j]的意义：在子串 s[i...j] 中，最长的回文子串长度。 #include <bits/stdc++.h> using namespace std; int longestPalindromeSubseq(const string& str) { i 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 ZeroYiAn
发表于 2023-04-11 19:54:23
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); while 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

动态规划 快手 字符串 算法工程师 2019
上传者：小小
难度：
23条回答 10685浏览

热门推荐

通过挑战的用户

查看代码

相关试题

回文字符串

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号