给定一个字符串，你的任务是计算这个字符串中有多少个回文子串（回文串是一个正读和反读都一样的字符串）。
具有不同开始位置或结束位置的回文串，即使是由相同的字符组成，也会被计为是不同的子串。
[编程题]回文子串
import java.util.ArrayList; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); String s = in.nextLine(); ArrayList<String> list = new ArrayList<>(); //longestPalindrome(s); for (int i = 0; i < s.length(); i++) { for (int j = i; j < s.length(); j++) { list.add(s.substring(i,j+1)); } } int cnt = 0; for(String temp : list) { if(isPalindrome(temp))cnt++; } System.out.println(cnt); } public static boolean isPalindrome(String s) { if(s.length() == 1) return true; StringBuilder sb = new StringBuilder(s); return sb.toString().equals(sb.reverse().toString()); } }
编辑于 2020-03-08 16:40:04
回复(0)
import java.util.Scanner;
/**
* @ClassName Main
* @Description TODO
* @Author Wlison
* @Date 2020/3/11 9:38
* @Version 1.0
**/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
String s = sc.nextLine();
int res = 0;
for (int i = s.length(); i > 0; i--) {
for (int j = 0; j < s.length()-i+1; j++) {
String temp = s.substring(j,i+j);
if (judge(temp))res++;
}
}
System.out.println(res);
}
}
public static boolean judge(String s){
char[] chs = s.toCharArray();
int len = s.length();
for (int i = 0; i < chs.length; i++) {
if (chs[i]!=chs[len-i-1])return false;
}
return true;
}
}
发表于 2020-03-12 09:50:18
回复(0)
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
string str;
cin >> str;
int len = str.length();
int count = 1;
for (int i = 1; i < str.length(); i++)
{
string x = "";
x+= str[i];
for (int j =1; j <= i;j++)
{
x+=str[i - j];
string tem = x;
reverse(tem.begin(), tem.end());
if (x == tem)
count++;
}
count++;
}
cout << count << endl;
return 0;
}
#include <string>
#include <algorithm>
using namespace std;
int main()
{
string str;
cin >> str;
int len = str.length();
int count = 1;
for (int i = 1; i < str.length(); i++)
{
string x = "";
x+= str[i];
for (int j =1; j <= i;j++)
{
x+=str[i - j];
string tem = x;
reverse(tem.begin(), tem.end());
if (x == tem)
count++;
}
count++;
}
cout << count << endl;
return 0;
}
发表于 2020-03-09 15:54:45
回复(0)
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
String s = scanner.next();
int cnt = 0;
boolean[][] dp = new boolean[s.length()][s.length()];
for(int i = s.length() - 1; i >= 0; i--){
for(int j = i; j < s.length(); j++){
if(i == j){
dp[i][j] = true;
}else if(i + 1 == j && s.charAt(i) == s.charAt(j)){
dp[i][j] = true;
}else{
dp[i][j] = dp[i + 1][j - 1] && s.charAt(i) == s.charAt(j);
}
if(dp[i][j])
cnt++;
}
}
System.out.println(cnt);
}
} dp[i][j]: 从下标 i 到 j 构成的字符串是否是回文串
发表于 2020-03-24 20:10:59
回复(0)
import java.util.Scanner;
public class Main{
public int helper(String str) {
int[] dp = new int[str.length()];
dp[0] = 1;
for (int i=1;i<str.length(); i++) {
for (int j=0;j<=i;j++) {
dp[i] += isPalindrome(str.substring(j,i+1));
}
dp[i] += dp[i-1];
}
return dp[str.length()-1];
}
private int isPalindrome(String str) {
if (str.length()==1) return 1;
int i=0, j = str.length()-1;
while(i<=j) {
if (str.charAt(i++) != str.charAt(j--)) return 0;
}
return 1;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String str1=null;
while (in.hasNext()) {
str1 = in.next();
}
int res = new Main().helper(str1);
System.out.println(res);
}
}
发表于 2020-03-22 18:58:30
回复(0)
#include <iostream>
#include <set>
#include <string>
#include <string.h>
using namespace std;
typedef pair<int, int> ValueType;
void judgeABA(const string &str, const int _max, int start, set<ValueType> &res)
{
int q = start - 1, p = start + 1;
while (q >= 0 && p < _max && str[q] == str[p])
{
res.insert(make_pair(q, p));
q--;
p++;
}
}
void judgeAA(const string &str, const int _max, int start, set<ValueType> &res)
{
int q = start, p = start + 1;
while (q >= 0 && p < _max && str[q] == str[p])
{
res.insert(make_pair(q, p));
q--;
p++;
}
}
int main()
{
string str;
cin >> str;
set<ValueType> res;
int len = str.length();
for (int idx = 0; idx < len; ++idx)
{
judgeAA(str, len, idx, res);
judgeABA(str, len, idx, res);
}
cout<<res.size() + len;
return 0;
}
发表于 2022-05-11 17:01:07
回复(0)
import java.util.Scanner;
public class Main{
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
char[] chs = s.toCharArray();
int count = 0;
//采用中心拓展法 或dp问题
for(int i = 0;i < chs.length;i ++){
count += expansion(chs,i,i);
count += expansion(chs,i,i+1);
}
System.out.println(count);
}
//function: 以chs中的索引left和right为中心开始拓展，找到以该索引为中心的回文串
public static int expansion(char[] chs,int left,int right){
if(left < 0 || right >= chs.length){
return 0;
}
if(chs[left] != chs[right]){
return 0;
}else{
return 1+expansion(chs,left - 1,right + 1);
}
}
}
public class Main{
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
char[] chs = s.toCharArray();
int count = 0;
//采用中心拓展法 或dp问题
for(int i = 0;i < chs.length;i ++){
count += expansion(chs,i,i);
count += expansion(chs,i,i+1);
}
System.out.println(count);
}
//function: 以chs中的索引left和right为中心开始拓展，找到以该索引为中心的回文串
public static int expansion(char[] chs,int left,int right){
if(left < 0 || right >= chs.length){
return 0;
}
if(chs[left] != chs[right]){
return 0;
}else{
return 1+expansion(chs,left - 1,right + 1);
}
}
}
发表于 2021-07-20 10:51:15
回复(0)
中心扩散法：
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String str = scanner.nextLine();
System.out.println(centerSpread(str));
}
/**
* 中心扩散法
*/
private static int count;
private static int centerSpread(String str) {
for (int i = 0; i < str.length(); i++) {
helper(str, i, i);
helper(str, i, i + 1);
}
return count;
}
private static void helper(String str, int left, int right) {
while (right < str.length() && left >= 0 && str.charAt(left) == str.charAt(right)) {
left--;
right++;
count++;
}
}
}
发表于 2020-10-25 14:18:08
回复(0)
s = input().strip() def countSubstrings(s): n = len(s) dp = [[False] * n for _ in range(n)] count = 0 for j in range(n): for i in range(0, j + 1): length = j - i + 1 if length == 1: dp[i][j] = True count += 1 if length == 2 and s[i] == s[j]: dp[i][j] = True count += 1 if length > 2 and s[i] == s[j] and dp[i+1][j-1] is True: dp[i][j] = True count += 1 return count print(countSubstrings(s))
发表于 2020-09-13 16:37:54
回复(0)
#include<iostream> //暴力解法
#include<string>
#include<vector>
using namespace std;
int r=0;
bool hui(string s,int start,int end)
{
while(start<end)
{
if(s[start]!=s[end])
return false;
start++;
end--;
}
return true;
}
void hui(string s,int start)
{
int count=0;
int end=s.size();
for(;end>=start;end--)
{
if(hui(s,start,end))
r++;
}
}
int main()
{
string s;
cin>>s;
for(int h=0;h<s.size();h++)
{
hui(s,h);
}
cout<<r<<endl;
return 0;
}
#include<string>
#include<vector>
using namespace std;
int r=0;
bool hui(string s,int start,int end)
{
while(start<end)
{
if(s[start]!=s[end])
return false;
start++;
end--;
}
return true;
}
void hui(string s,int start)
{
int count=0;
int end=s.size();
for(;end>=start;end--)
{
if(hui(s,start,end))
r++;
}
}
int main()
{
string s;
cin>>s;
for(int h=0;h<s.size();h++)
{
hui(s,h);
}
cout<<r<<endl;
return 0;
}
编辑于 2020-08-17 20:26:53
回复(0)
import java.util.Scanner;
public class Main{
public int numOfHuiwen(String s){
int res = 0;
if(s == null || s.length()==0) return res;
for(int i=0;i<s.length();i++){
res+=centerSpread(s,i,i);
res+=centerSpread(s,i,i+1);
}
return res;
}
public int centerSpread(String s, int i, int j){
int count = 0;
while(i>=0 && j<s.length()){
if(s.charAt(i)==s.charAt(j)){
count++;
i--;
j++;
}
else break;
}
return count;
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
String s = sc.next();
Main so = new Main();
int res = so.numOfHuiwen(s);
System.out.println(res);
}
}
发表于 2020-07-31 15:40:13
回复(0)
public static boolean justify(String input) {
int head = 0;
int tail = input.length() - 1;
while(head < tail) {
if(input.charAt(head) == input.charAt(tail)) {
head++;
tail--;
}else {
return false;
}
}
return true;
}
public static int collect(String input) {
int output = 0;
for(int i = 0; i <= input.length(); i++) {
for (int j = i + 1; j <= input.length(); j++) {
if(justify(input.substring(i, j))) {
output++;
}
}
}
return output;
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
while(input.hasNext()) {
String s = input.nextLine();
System.out.println(collect(s));
}
}
编辑于 2020-04-14 12:52:35
回复(0)
import java.util.Scanner;
//中心扩散法
public class Main {
public static int count = 0;
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
String str = s.nextLine();
for(int i=0;i<str.length();i++){
checkVaild(str,i,i);
checkVaild(str,i,i+1);
}
System.out.println(count);
}
public static void checkVaild(String str,int left,int right){
while(left>=0 && right<str.length() && str.charAt(left) == str.charAt(right)){
left--;
right++;
count++;
}
}
}
发表于 2020-04-09 16:07:56
回复(0)
#include<cstdio>
#include<cstring>
int main(){
char s[1005];
scanf("%s",s);
int count=0,len = strlen(s);
for(int i=0; i<len ;i++){
for(int j=len-1; j>=i; j--){
int a,b;
for(a=i,b=j; a<=b && s[a]==s[b]; a++,b--);
if(a>b) count++;
}
}
printf("%d",count);
return 0;
}
编辑于 2020-03-31 16:49:51
回复(3)
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String a = sc.nextLine();
char[] text = a.toCharArray();
int hwNum = text.length;
for (int i = 0; i < text.length-1; i++) {
for (int j = i+1; j < text.length; j++) {
boolean flag = judgeHw(text,i,j);
if(flag) {
hwNum++;
}
}
}
System.out.println(hwNum);
}
private static boolean judgeHw(char[] text, int i, int j) {
while(i < j) {
if(text[i++] != text[j--]) {
return false;
}
}
return true;
}
}
发表于 2020-03-31 11:29:33
回复(0)
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
String s = in.nextLine();
int res = 0;
//dp[i][j] 代表从index i 到j是否是回文子串
boolean dp[][] = new boolean[s.length()][s.length()];
for (int i = 0; i < s.length(); i++) {
for (int j = 0; j <= s.length() - i - 1; j++) {
//两边的字符相等，则判断中间是否为回文。
if (s.charAt(j) == s.charAt(i + j)) {
if(i < 2 || dp[j+1][j+i-1]){
dp[j][i+j] = true;
res++;
}
}
}
}
System.out.println(res);
}
}
发表于 2020-03-25 15:40:29
回复(0)
import java.util.Scanner;
/ *
*.根据回文串的特点
*.若一个回文子串的长度为i*.分别对于i&1==1or0，其i+2长度的回文子串必为同一位置下i长度的子串的超集
*.则其i+2回文子串的最左端必等于最右端
*.这就简化了子串的判断方法
*.每次i长度的子串是否回文，只需要判断两个条件：
*1.同一中心位置下的i-2长度子串是否为回文子串
*2.此子串最左端是否等于最右端
*
*.这明显满足最优子结构性质
*.并且当前子问题最优解状态是确定的，true or false，满足无后效性
*
*.状态转移方程为：
*.bary[i][j] = ary[j]==ary[j+1]; i==1//子串长度为2
*.bary[i][j] = bary[i-2][j]&&ary[j-i/2]==ary[j+i/2]; i%2==0//此时子串长度为奇数
*.bary[i][j] = bary[i-2][j]&&ary[j-(i+1)/2+1]==ary[j+(i+1)/2]; i%2==1,i!=1;//此时子串长度为偶数且长度不为2
*
*.对于这个题目，要求的是回文子串的数量，我们只需要在每次判定是回文子串的地方记录即可
*
*/
public class Main{
public static void Main(String args[]) {
Scanner s = new Scanner(System.in);
String str = s.nextLine();
char[] ary = str.toCharArray();//转换成字符数组再操作int n = ary.length;
boolean[][] bary = new boolean[n][n];//用于记录子问题的解——当前子串的i-2子串是否回文
for(int i=0;i<n;i++)//初始化，第0行的回文串长度为0，必回文
bary[0][i] = true;
int count = n;//0行每个字母都是回文
for(int i=1;i<n;i++) {
for(int j=i/2;j<(n-(i-1)/2-1);j++) {
if(i==1) {//按照状态转移方程，第1行（长度为2）需单独处理
if(ary[j]==ary[j+1]) {//直接当前字符比较下一字符
count++;
bary[i][j] = true;
}
continue;
}
/*
* 这里略长
* 第一个条件bary[i-2][j]既是保证当前位置下的子串回文，才进行后面的判断
*长度为奇数和偶数（i%2==0 or 1）的最左端和最右端索引是不同的，需分别
*ary[j-i/2]==ary[j+i/2]为奇数长度的子串
*ary[j-(i+1)/2+1]==ary[j+(i+1)/2]为偶数长度的子串
*/
if(bary[i-2][j]&&(i%2==0?(ary[j-i/2]==ary[j+i/2]):ary[j-(i+1)/2+1]==ary[j+(i+1)/2])) {
count++;
bary[i][j] = true;
}
}
}
//输出最大回文子串数量
System.out.println(count);
}
}
发表于 2020-03-24 20:56:23
回复(0)
Python
用的动态规划加上正儿八经回文情况
import sys s=sys.stdin.readline().strip() n=len(s) dp=[1]*n #动态规划+真儿八斤的回文情况 for i in range(1,n): if s[i-1]!=s[i]:(3345)#不相等即无法构成回文，只能单字 dp[i]=dp[i-1]+1#动态规划第二个与前一个不相同 a\ab\abc的普通情况 for k in range(i):(3346)#a\ab\aba 或者noon或者level情况 te=s[k:i+1] if te==te[::-1]: dp[i]=dp[i]+1 else: j=i count=2 while j>1:#a\aa\aaa\abaa第二个字符与前一个相同的情况（看相同几次） if s[j-1]==s[j-2]: count+=1 j-=1 else: break dp[i]=dp[i-1]+count print(dp[-1])
发表于 2020-03-22 23:01:15
回复(0)
| |
import java.util.*;
public class Main {
public static boolean isrestr(String str){
StringBuilder stringBuilder = new StringBuilder(str);
if(stringBuilder.reverse().toString().equals(str)){
return true;
}else {
return false;
}
}
public static void main(String[] args) {
// //滑动窗口
int len = 1;
int count = 0;
Scanner in = new Scanner(System.in);
String str = in.nextLine();
for(len=1;len<=str.length();len++) {
for (int i = 0; i < str.length(); i++) {
if((i+len)>str.length())break;
String now = str.substring(i,i+len);
if(isrestr(now)==true){
count++;
}
}
}
System.out.println(count);
}
}
发表于 2020-03-12 17:26:05
回复(0)
问题信息
通过挑战的用户
-
2022-11-01 17:23:45
-
2022-10-16 14:43:56 -
2022-09-16 21:43:53
-
2022-09-10 13:50:16
-
2022-09-03 19:47:21
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
