回文子串

正文索引 [隐藏]

题目描述:

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

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

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

可用C++,Java,C#实现相关代码逻辑

输入描述:

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

输出描述:

符合条件的字符串有”a”,”a”,”aa”,”b”,”c”,”b”,”bcb” 所以答案:7。

输入样例:

aabcb

输出样例:

7

解题思路:

快手校招题。牛客网贴的标签是dp,不要跟我说什么dp😆无脑暴力破解就完事啦,我赌它不会TLE,一提交代码还真AC。

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define Up(i,a,b) for(int i = a; i <= b; i++)

bool fun(string s)   //判断是不是回文字符串
{
    string t = s;
    reverse(t.begin(),t.end());   //翻转字符串
    return s==t;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    string str;
    getline(cin,str);
    int len = str.length();
    int cnt = 0;   //回文子串的个数
    Up(i,0,len-1)      //暴力破解就完事啦,看会不会TLE
    {
        Up(j,i+1,len)
        {
            string t = str.substr(i,j-i);
            // cout << t << endl;
            if(fun(t)) cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}