首页 > 试题广场 >

回文子串

[编程题]回文子串
  • 热度指数:8563 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
给定一个字符串,你的任务是计算这个字符串中有多少个回文子串。
("回文串”是一个正读和反读都一样的字符串,比如“level”或者“noon”等等就是回文串。)
具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被计为是不同的子串。

数据范围:字符串长度满足  

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


输出描述:
符合条件的字符串有"a","a","aa","b","c","b","bcb"

所以答案:7
示例1

输入

aabcb

输出

7

字符串的回文串总结

一看到回文字符串,脑海里立马要想到前面两个最常用的结题思路:

  • 1.动态规划
  • 2.中心扩散法
  • 3.还有著名的马拉车算法

leetcode出现的回文字符串的三个题:

  • 1.回文子串的个数
  • 2.最长回文子串
  • 3.最长不连续的回文子串

1.回文子串的个数——本题

public class Solution14_回文子串 {
    /**
     * 方法一:中心扩散法
     */
    static int ans = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String s = bf.readLine();
        for (int i = 0; i < s.length(); i++) {
            //考虑两种情况:aba 和 abba
            centerSpread(s, i, i);
            centerSpread(s, i, i + 1);
        }
        System.out.println(ans);
    }

    //判断回文串的中心扩散法
    private static void centerSpread(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
            ans++;
        }
    }

    //方法二:动态规划
    private static int dp(String s) {
        int n = s.length(), ans = 0;
        boolean[][] dp = new boolean[n][n];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                dp[i][j] = (s.charAt(i) == s.charAt(j)) && (j - i <= 2 || dp[i + 1][j - 1]);
                if (dp[i][j]) ans++;
            }
        }
        return ans;
    }
}

2.最长回文子串

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:
Input: "cbbd"
Output: "bb"

class Qusetion2 {

    //1.动态规划
    public static String longestPalindrome(String s) {
        int n = s.length();
        if (n < 2) return s;
        int maxLen = 1;
        String res = s.substring(0, 1);
        boolean[][] dp = new boolean[n][n];
        //左边界一定小于右边界,因此从右边界开始
        for (int r = 1; r < n; r++) { //表示右边界
            for (int l = 0; l < r; l++) { //表示左边界
                // 区间应该慢慢放大
                // 状态转移方程:如果头尾字符相等并且中间也是回文
                // 在头尾字符相等的前提下,如果收缩以后不构成区间(最多只有 1 个元素),直接返回 True 即可
                // 否则要继续看收缩以后的区间的回文性
                if (s.charAt(l) == s.charAt(r) && ((r - l) <= 2 || dp[l + 1][r - 1])) {
                    dp[l][r] = true;
                    if (r - l + 1 > maxLen) {
                        maxLen = r - l + 1;
                        res = s.substring(l, r + 1);
                    }
                }
            }
        }
        return res;
    }

    //2.中心扩展法
    private int start, maxLen;

    public String longestPalindrome1(String s) {
        if (s == null || s.length() < 2) return s;
        for (int i = 0; i < s.length(); i++) {
            //考虑中心扩散的两种情况1:aba  和 2: bb
            findMaxPalindrome(s, i, i);
            findMaxPalindrome(s, i, i + 1);
        }
        return s.substring(start, start + maxLen);
    }

    private void findMaxPalindrome(String s, int i, int j) {
        while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
            i--;//向左延伸
            j++;//向右延伸
        }
        //记录每个起始点扩展的回文串的最大长度
        if (maxLen < j - i - 1) {
            start = i + 1;
            maxLen = j - i - 1;
        }
    }
}

3.最长不连续回文子串

Given a string s, find the longest palindromic subsequence's length in s. You may assume that the maximum length of s is 1000.
Example 1:
Input:
"bbbab"
Output:
4
One possible longest palindromic subsequence is "bbbb".

    public int longestPalindrome(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];//dp[l][r]表示l-r中的最长回文串
        for (int r = 0; r < n; r++) {
            dp[r][r] = 1;
            for (int l = r - 1; l >= 0; l--) {
                if (s.charAt(l) == s.charAt(r)) {
                    dp[l][r] = dp[l + 1][r - 1] + 2;
                } else {
                    dp[l][r] = Math.max(dp[l + 1][r], dp[l][r - 1]);
                }
            }
        }
        return dp[0][n - 1];
    }
发表于 2019-08-05 13:22:12 回复(0)
dp解法。记dp[i][j]为s索引从i到j的的子串是否为回文字符串。
若j-i>=2,那么dp[i][j]=dp[i+1][j-1]&&s[i]==s[j];因此推断i的遍历为降序,而j的遍历为升序,又有i到j的子串,所以i<=j;    若j-i==1,dp[i][j]=s[i]==s[j];    若j==i,dp[i][j]=true。
在求每个dp[i][j]时判断其是否为true,并记录true的个数即可。
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main()
{
    string s;
    cin>>s;
    int n=s.size();//字符串长度
    vector<vector<bool>> dp(n,vector<bool>(n,0));//dp[i][j] 从i到j的子串是否为回文串
    int res=0;//记录回文子串的个数
    for(int i=n-1;i>=0;i--)//i降序
        for(int j=i;j<n;j++)//j升序 且j>=i
        {
            if(i==j)
                dp[i][j]=true;//一个字母是回文字符串
            else if(j-i==1)//首尾相邻
            {
                if(s[i]==s[j])
                    dp[i][j]=true;//相同为回文
                else
                    dp[i][j]=false;//不同不为回文
            }
            else//首尾不相邻
            {
                if(dp[i+1][j-1]==true&&s[i]==s[j])//中间为回文且首尾相同为回文
                    dp[i][j]=true;
                else
                    dp[i][j]=false;//否则不为回文
            }
            if(dp[i][j]==true)
                res++;//记录回文子串的个数
        }
    cout<<res<<endl;
    return 0;
}

发表于 2019-07-16 23:27:20 回复(0)
//不喜欢dp的看这里
#include <iostream>
#include <string>
using namespace std;
int main()
{
    string str;
    while (cin >> str)
    {
        int len = str.size();
        int count = 0;
        for (int i = 1; i<len; i++)
        {
            if (str[i - 1] == str[i + 1])
            {
                count++;
                for (int j = 1; j <= (len - i) && j<i; j++)
                {
                    if (str[i +1+ j] == str[i - 1 - j])
                    {
                        count++;
                    }
                    else
                    {
                        break;
                    }
                }
            }
            if (str[i] == str[i - 1])
            {
                count++;
                for (int j = 1; j <= (len - i) && j<i; j++)
                {
                    if (str[i + j] == str[i - 1 - j])
                    {
                        count++;
                    }
                    else
                    {
                        break;
                    }
                }
            }
        }
        cout << count + len << endl;
    }
    return 0;
}

发表于 2019-07-04 21:24:06 回复(1)
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.next();
        // 从中心向两边扩散
        int result = 0;
        int i = 0;
        while (i < input.length()) {
            // 以i位置的字符为中心
            // 首先i位置字符本身肯定是一个回文串
            result++;
            for (int j = 1; i - j >= 0 && i + j < input.length(); ++j) {
                if (input.charAt(i - j) == input.charAt(i + j)) {
                    ++result;
                } else {
                    break;
                }
            }

            // 以i右边的间隔为中心
            // 若i是最后一个字符就无需进行这一步了
            if (i == input.length() - 1) {
                break;
            }
            for (int j = 0 ; i - j >= 0 && i + j + 1 < input.length(); ++j) {
                if (input.charAt(i - j) == input.charAt(i + j + 1)) {
                    ++result;
                } else {
                    break;
                }
            }
            ++i;
        }
        System.out.println(result);
    }
}
发表于 2020-02-16 12:36:44 回复(0)
/*
数据小,暴力判断应该也可以过。
动态规划。
dp[i]表示前i个字符中包含的回文子串。
dp[i] = dp[i-1] + 新增。
突然想到:这样写和暴力完全没区别。
*/
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.next();
        int len = s.length();
        int[] dp = new int[len + 1];   //表示前i个字符中有多少个回文子串。
        dp[0] = 0;
        dp[1] = 1;
        int cnt = 0;   //记新加一个字符增加的回文子串数量。
        for (int i = 2; i <= len; i++) {
            cnt = 0;
            for (int loc = 0; loc < i - 1; loc++) {
                if (s.charAt(loc) == s.charAt(i - 1)) {
                    if (isBackString(s.substring(loc, i)))
                        cnt++;
                }
            }
            dp[i] = dp[i - 1] + cnt + 1;
        }
        System.out.println(dp[len]);
    }

    static boolean isBackString(String s) {
        int len = s.length();
        int head = 0;
        int end = len - 1;
        while (head < end) {
            if (s.charAt(head) != s.charAt(end))
                return false;
            head++;
            end--;
        }
        return true;
    }
}

发表于 2019-06-29 10:48:23 回复(0)
首次做回文子串类的题,第一想到的方法就是暴力破解。解题思路
1.首先,把所有的子字符串全部遍历出来,1位\2位、3位...n位
2.利用字符串反转来验证分解出来的哪些子串是回文子串,即翻着读与正着读都一样的,那么就是rever后的串与原子串相等。(我们使用s[::-1]切片来反转)
3.使用count统计正串与反串相等的个数
s=input().strip()
count = 0
for i in range(len(s)):
    j=i+1
    while j<=len(s):
        ssub=s[i:j]
        if ssub==ssub[::-1]:
            count+=1
        j += 1
print(count)

当然有高规格的解题方法比如:动态规划、中心扩展。继续探索中
发表于 2021-03-12 17:32:48 回复(0)
根据题意,由于单个字符(不去重)也算回文串,因此给定字符串至少有str.length()个符合要求的字符串。从长度为2的子串开始,直接检查所有子串是否满足回文性即可。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine().trim();
        int res = str.length();
        for(int len = 2; len <= str.length(); len++){
            for(int start = 0; start + len <= str.length(); start++)
                if(judge(str, start, start + len - 1)) res ++;
        }
        System.out.println(res);
    }
    
    private static boolean judge(String str, int left, int right) {
        while(left < right){
            if(str.charAt(left) != str.charAt(right)) return false;
            left ++;
            right --;
        }
        return true;
    }
}


发表于 2021-02-19 14:31:39 回复(0)
//算是暴力破解
//稍作改进:对于单个字符不做判断,它们本身就是回文子串

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)
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)
记录
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)
//就硬解
#include <stdio.h>
#include <string.h>
int main(){
    char s[50],len;
    scanf("%s", &s);
    len = strlen(s);
    int count1 = 0;
    /*
    采用遍历的方式,以当前位置为起点不断增加字符串的长度
    对这一段字符串进行是否为回文的判断(首位与末尾,首位不断推后,末尾不断推前)
    中间如若有一对字符对不上则这一段判断结束
    只有当这部分字符串全部都被判断后,才能认为此段为回文,计数+1
    */
    for(int i = 0; i < len;i++){
        for(int j = 1;j+i < len;j++){
            for(int k = 0;i+k<=i+j-k+1;k++){
                if(s[i+k] != s[i+j-k])
                    break;
                if(2*k >= j)
                    count1++;
            }
        }
    }
    printf("%d",count1+len);  //回文数加上字符串长度
    return 0;
}

编辑于 2020-02-28 16:21:41 回复(0)
#include <bits/stdc++.h>
using namespace std;

int F(string s){
    int l = s.length();
    int i=0,j=l-1;
    while(i<l)
        if(s[i++]!=s[j--])
            return 0;
    return 1;
}

int main(){
    string s;
    cin>>s;
    int n = s.length(), r=n;
    for(int i=0;i<n;i++){
        for(int l=2;i+l<=n;l++){
            string t = s.substr(i, l);
            r += F(t);
        }
    }
    cout<<r<<endl;
    return 0;
}

发表于 2019-11-07 00:42:55 回复(0)
// 数据量为 50, 因此可用 O(N^3)

#include<bits/stdc++.h>
using namespace std;
string str;
bool f(int l, int r) {
	while (l < r) {
		if (str[l++] != str[r--]) {
			return false;
		}
	}
	return true;
}
int main() {
	cin >> str;
	auto lens = str.length();
	int ans = lens;
	for (auto len = 2; len<=lens; ++len) {
		for (int i=0; i+len-1<lens; ++i) {
			if (f(i, i+len-1)) {
				++ans;
			}
		}
	}
	cout << ans << endl;
	return 0;
}

发表于 2019-10-22 16:59:24 回复(0)
直接蛮力法
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)
/*
暴力枚举 
*/
#include<bits/stdc++.h>
using namespace std;
#define N 1000

int main()
{
//    freopen("input.txt", "r", stdin);
    int n, i, j, k, ans = 0;
    char s[N];
    cin >> s;
    n = strlen(s);
    for(k = 0; k < 2 * n - 1; k++) {
        i = int(k / 2);
        j = k - i;
        while(i >= 0 && j < n && s[i] == s[j]) {
            ans++;
            i--;
            j++;
        }
    }
    cout << ans << endl;
    return 0;
}

发表于 2019-07-10 11:08:10 回复(0)
str = input()

#  判断是否是回文
def is_palindrome(str):
    is_palindrome_flag = True
    for i in range(len(str) // 2):
        if str[i] is not str[-i - 1]:
            is_palindrome_flag = False
    return is_palindrome_flag

res = 0
# 将str变成二维,找到str[x:y+1]的切片
for x in range(0, len(str)):
    for y in range(x, len(str)):
        if is_palindrome(str[x:y + 1]):
            res += 1

print(res)

发表于 2019-09-17 10:10:50 回复(0)

import java.util.*;
public class Main {
public static void main(String[] args){
Scanner sc= new Scanner(System.in);
String str = sc.next();
int sum=0;
for (int i = 0; i < str.length(); i++)
for (int j = i+1; j <=str.length(); j++)
{
String str1=str.substring(i, j);
if(str1.equals( new StringBuffer(str1).reverse().toString()))
sum++;
}
System.out.println(sum);
}
}
算是暴力枚举了,中间感觉还可以优化一些,就是借助java的函数,截取字符,然后翻转对比!

其实还有一种开枝散叶的算法,就是每次以一个字符为中心,先往右看,找相同的,如果有,就每找到一个就总数加1,直到找不到了,然后再看左边有没有使得左右相等的。这个代码也不复杂!我就不写了,有想法的可以实现下!

比如给的例子:aabcb

先加赋值sum等于字符串的长度,先把每个单独字符成的回文算下,这时候sum=5:

先从第一个a看,右边有一个跟它一样的,所以sum++,sum这时为6.

再往后看,一个b,不符合。

然后往左边看,左边没有了。好,看第二个字符。

第二个字符是a,同样,右看,没有!

左看,a和右边的b不相等!

看下一个,也就是b

右看,b不等于c,没有!

左看,a和c不相等,没有!

然后看c,右看,没有!

左看!b等于b!好sum++,这时sum=7;

继续左看,右边跑数组外面去了,不符合!

再看最后那个b,右边跑数组外面去了,不符合!

看左边,右边跑出去了,不符合!

这样就完了吧!

呵呵,还没完,中间有个坑,要填一下,如aaa,第一个里a往右看有个aaa,第二个a往左看,左右有个aaa,这不是就重复计算了么?

所以往左看的时候,要仔细判断!

这个自己解决下吧!

编辑于 2019-07-12 16:03:00 回复(2)
import sys
def isHuiwen(string):
    if len(string)==1:
        return True
    i,j = 0,len(string)-1
    while i<j:
        if string[i] != string[j]:
            return False
        i+=1
        j-=1
    return True
def countNum(string):
    res = 0
    for i in range(len(string)-1,-1,-1):
        if isHuiwen(string[i:len(string)]):
            res+=1
    return res
while True:
    #动态规划问题:
    #dp[i]表示在第i个位置时字符串有多少个回文子串
    #状态转移方程:
    #dp[i+1] = dp[i] + countNum(str[:i])
    string = input().strip()
    dp=[0 for _ in range(len(string))]
    dp[0]=1
    for i in range(1,len(string)):
        dp[i] = dp[i-1]+countNum(string[:i+1])
    print(dp[-1])

发表于 2020-08-19 22:25:48 回复(0)
def num_substr(s):
    res = 0
    if len(s)<=1:
        print(len(s))
        return len(s)
    for length in range(len(s),0,-1):
        for i in range(len(s)-length+1):
            now_s = s[i:i+length]
            if now_s == now_s[::-1]:
                res+=1
    print(res)
    return res

if __name__ == '__main__':
    import sys
    s = sys.stdin.readline().strip()
    num_substr(s)

发表于 2020-06-11 12:47:08 回复(0)

最长回文串的变型

#include <iostream>
(720)#include <vector>
#include <string>
using namespace std;

int main(){

    string s;
    cin >> s;
    int len = s.size();
    int ans = 0;
    vector<vector<int>> dp(len,vector<int>(len,0));
    for(int i = 0;i < len;i++){
        dp[i][i] = 1;
        ans++;
    }
    for(int i = len-2;i >= 0;i--){
        for(int j = i+1;j <= len-1;j++){
            if(s[i] == s[j]){
                dp[i][j] = dp[i+1][j-1] + 2;
            }else{
                dp[i][j] = max(dp[i+1][j],dp[i][j-1]);
            }
            if((j-i+1) == dp[i][j]){
                ans++;
            }
        }
    }
    cout << ans;
    return 0;
}
发表于 2020-05-16 12:42:55 回复(0)