我要招人

去企业版

首页 > 试题广场 >

回文子串

[编程题]回文子串

热度指数：8589 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

("回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。)

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。

数据范围：字符串长度满足 $1 \le n \le 50 \$

输入描述:

输入一个字符串S 例如“aabcb”(1 <= |S| <= 50), |S|表示字符串S的长度。

输出描述:

符合条件的字符串有"a","a","aa","b","c","b","bcb"

所以答案:7

示例1

输入

aabcb

输出

算法知识视频讲解

Java

工大月

//算是暴力破解

//稍作改进：对于单个字符不做判断，它们本身就是回文子串

import java.util.Scanner;

public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
String input = sc.nextLine().trim();
int len = input.length();
int totalLen = len;//每个字符都是回文子串，所以最少回文子串是字符串的长度

for(int j = 0; j < len; j++){
String temp = input.substring(j, len);
for(int i = 1; i < temp.length(); i++){
String str = temp.substring(0, i+1);
StringBuffer sb = new StringBuffer(str);
if(str.equals(sb.reverse()+"")){//利用reverse方法，判断是否为回文子串
totalLen++;
}
}
}
System.out.println(totalLen);
}
}

发表于 2020-06-17 13:42:37 回复(0)

Java

lmz9509

import java.util.*;
/*
利用indexof和substring方法来进行操作
依次把首尾相同的字符串进行回文数判断
*/
public class Main{
    public static boolean isHui(String str){
        if(str.length()<=1)return true;
        int left = 0,right = str.length()-1;
        while(left<right){
            if(str.charAt(left)==str.charAt(right)){
                left++;
                right--;
            }else
                return false;
        }
        return true;
    }
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        String str = input.next();
        int count = str.length();
        for(int i = 0;i<str.length()-1;i++){
            String substr = str.substring(i+1);
            while(substr.contains(Character.toString(str.charAt(i)))){
                String subsubstr = substr.substring(i,substr.indexOf(str.charAt(i))+1);
                if(isHui(subsubstr))
                    count++;
                substr = substr.substring(substr.indexOf(str.charAt(i))+1);
            }
        }
        System.out.println(count);
    }
    
}

请教下大神们，我这种方法为什么会只有30%，系统后面会报错呢？实在想不明白哪里出问题了，求解答

发表于 2020-04-18 13:14:03 回复(0)

Java

LHC0512

记录

import java.util.Scanner;

/**
 * 运行时间：45ms
 *
 * 占用内存：10548k
 * */
public class Main {

    static  int count=0;
    static String s;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        s = scanner.next();
        for (int i = 0; i < s.length(); i++) {
            ////考虑两种情况：aba 和 abba
            centerSpread(i,i);
            centerSpread(i,i+1);
        }
        System.out.println(count);
    }

    static void centerSpread(int i,int j){
        while (i>=0&&j<s.length()&&s.charAt(i)==s.charAt(j)){
            count++; i--; j++;
        }
    }

}

发表于 2020-03-01 12:09:32 回复(0)

Java

呃。。。

直接蛮力法

public class Main {
    //蛮力法
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        int n = str.length();
        int count = n;
        for (int i=0;i<n;i++){
            for (int j=i+1;j<n;j++){
                if (judge(str,i,j))
                    count++;
            }
        }
        System.out.println(count);
    }
    private static boolean judge(String str,int i,int j){
        while (i < j){
            if (str.charAt(i) != str.charAt(j))
                return false;
            i++;j--;
        }
        return true;
    }
}

动态规划

dp[i][j]表示从i到j之间是否为回文串，若为回文串则dp[i][j]=1,初始时，即i==j时，dp[i][j]=1，其他情况下，dp[i][j]=1则要求str.charAt[i]==str.charAt[j]且dp[i+1][j-1]==1，注意 i<=j！

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        int n = str.length();
        int count = n;
        int[][] dp = new int[n][n];
        dp[0][0] = 1;
        for (int j=1;j<n;j++){
            dp[j][j] = 1;
            for (int i=j-1;i>=0;i--){
                if (str.charAt(i) == str.charAt(j) && (i+1 > j-1 || dp[i+1][j-1] == 1)){
                    dp[i][j] = 1;
                    count++;
                }
            }
        }
        System.out.println(count);
    }
}

发表于 2019-08-02 14:59:06 回复(0)

Java

Naples520

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
    Scanner input = new Scanner(System.in);
    String string = input.nextLine();

    // 1.单个字符均是回文串(可合并到2.中)
    int count = string.length();
    
    // 找到对称轴，向两边同步扩展，可找到所有回文串
    // 2.对称轴在元素上面
    for (int i = 0; i < string.length(); i++) {
        int max = i < string.length() / 2 ? i : string.length() - 1 - i;
        for (int j = 1; j <= max; j++) {
            if (string.charAt(i - j) == string.charAt(i + j)) count++;
            else break;
        }
    }
    // 3.对称轴在元素中间
    for (int i = 0; i < string.length(); i++) {
        int max = i < string.length() - i ? i : string.length() - i;
        for (int j = 1; j <= max; j++) {
            if (string.charAt(i - j) == string.charAt(i + j - 1)) count++;
            else break;
        }
    }
    System.out.println(count);
    }
}

编辑于 2019-08-02 12:12:39 回复(0)

Java

Kangk

import java.util.Scanner;
import java.util.Arrays;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
String[] str=sc.nextLine().split("");
int n=str.length;
int backtext=0;
for(int i=0;i<n;i++){
String[] s=Arrays.copyOfRange(str,i,n);
for(int y=0;y<s.length;y++){
int m=Check(Arrays.copyOfRange(s,0,y+1));
backtext=backtext+m;
}

}
System.out.print(backtext);
}
static int Check(String[] str){
int m=str.length;
for(int i=0;i<m/2;i++){
if(str[i].equals(str[m-i-1]))
continue;
else
return 0;
}
return 1;
}
}

发表于 2019-07-19 15:28:50 回复(0)