[牛课习题]判断字符串是否回文及统计回文

题目描述

“回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。花花非常喜欢这种拥有对称美的回文串，生日的时候她得到两个礼物分别是字符串A和字符串B。现在她非常好奇有没有办法将字符串B插入字符串A使产生的字符串是一个回文串。你接受花花的请求，帮助她寻找有多少种插入办法可以使新串是一个回文串。如果字符串B插入的位置不同就考虑为不一样的办法。
例如：
A = “aba”，B = “b”。这里有4种把B插入A的办法：
在A的第一个字母之前: "baba" 不是回文
在第一个字母‘a’之后: "abba" 是回文
在字母‘b’之后: "abba" 是回文
在第二个字母'a'之后 "abab" 不是回文
所以满足条件的答案为2

输入描述:

每组输入数据共两行。
第一行为字符串A
第二行为字符串B
字符串长度均小于100且只包含小写字母

输出描述:

输出一个数字，表示把字符串B插入字符串A之后构成一个回文串的方法数
示例1
输入
aba
b
输出
2

题目分析：

首先我们要搞清楚什么是回文串，回文串就是从左边和右边同时看读出的数据是相同的，比如noon和level。level这类字符比较特殊，按照代码思路要注意看需不需要特殊处理
判断回文很简单，定义两个位置，start和end去遍历字符串，从str的start和end各取一个字符，如果不相等直接返回false，说明他不是回文串，相等则start++，end--进行下一位置的判断，循环结束条件就是start <= end，等于的情况就相当于上面level中的v字符。
统计构成回文串的方法数，这里我直接使用的是暴力破解，定义一个临时字符串保存str1的值，把str2插入到tmp的各个位置进行判断，如果是回文串，count++，最后输出count数就行了。这里需要注意的是插入的位置，从0 <= i <= str1.size() 都是可以的，一定要注意取等号时的str1.size()，不然可能无法通过测试用例。

代码如下：

#include <iostream>#include <string>using namespace std;bool isCircle(string str){    size_t start = 0;    size_t end = str.size()-1;    while(start <= end)    {        if(str[start] != str[end])            return false;        start++;        end--;    }    return true;}int main(){    string str1, str2;    int count = 0;    while(cin >> str1 >> str2)    {        int sz = str1.size();        for(size_t i = 0; i <= sz; ++i)        {            string tmp = str1;            tmp.insert(i, str2);            if(isCircle(tmp))                count++;        }        cout << count << endl;    }    return 0;}

更多相关文章

随机推荐