回文串问题分析

HDU CS505  实验室

与各位共享~

今天学长让我做一道编程题：
        描述：一个字符串如“coco”，向其添加一个字符组成一个新的字符串，这个字符串可能会成为回文字符串。
        输入：一个不超过10位长度的字符串
        输出：向输入的字符串添加一个字符，判断产生的新字符串是否有可能是回文串，若是，则输出“YES”，否输出“NO”

分析：
    首先想到的是穷举法，把添加一个字符后的所有新字符串都列出来，逐一判断是否是回文串。
    
    添加的字符，理论上可以是任意字符，但是如果要尽可能使得生产的字符串是回文串，那么这个被添加的字符一般是输入字符串中含有的字符（本身是回文串，且位数是偶数的，可以在中间添加任意字符，此时新字符串都是回文串）。

    所以，要提取出输入字符串中不同的字符，然后根据字符生成新的字符串。设输入字符串长度是Len，根据插入位置，每个字符可以得到Len+1个新字符串。如果从输入字符串中提取到的不同字符个数是n（n<=Len）,那么生成的字符串总数是（Len+1）*n。又Len<=10,所以问题的最大规模为110个新字符串。
    
优化：
       1、 输入字符串后，首先检测它是不是回文串，如果是回文串而且位数是偶数，那么直接输出“YES”，否则穷举判断
        2、另外，穷举时，生成一个判断一个，一旦有一个是回文串，就停止生成，输出结果，程序结束。

代码（C++实现，代码只用了优化1）：
用时：半小时~1小时，非专业ACM的人士

#include <iostream>
#include <string>
#include <vector>
using namespace std;
 
bool isHuiWenString(string &str)
{
    for(int i=0,j=str.length()-1;i<str.length()/2+1;i++,--j)
    {
        if(str[i]!=str[j])
            return false;
    }
    return true;
}
 
bool existInVector(char ch,vector<char> &vec)
{
    bool flag=false;
    if(vec.empty())
        return flag;
    for(vector<char>::iterator it = vec.begin();it!=vec.end();++it)
        if(ch == *it){
            flag = true;
            break;
        } 
    return flag;
}
 
bool existHuiWenVector(vector<string>& vstr)
{
    bool flag=false;
    if(vstr.empty())
        return flag;
    for(vector<string>::iterator it=vstr.begin();it!=vstr.end();it++)
    {
        if(isHuiWenString(*it)){
            flag = true;
            break;
        } 
    }
    return flag;
}
 
int main()
{
    string str;
    cin>>str;
    //如果是回文串且偶数位数
    if(0 == str.length()%2 && isHuiWenString(str)){
        cout<<"YES"<<endl;
        return 0;
    }
 
    //提取不同字符数
    vector<char> charVec;
    for(int i=0;i<str.length();i++)
        if(!existInVector(str[i],charVec))
            charVec.push_back(str[i]);
    vector<string> vStr;
    //getAllKindsString(vStr,charVec,str);
    vector<char> vChar=charVec;
 
    //生成待检测的所有新字符串
    for(vector<char>::iterator ic=vChar.begin();ic!=vChar.end();++ic)
    {
        string temp = *ic+str;
        vStr.push_back(temp);
        temp =str+*ic;
        vStr.push_back(temp);
        for(int i=1;i<str.length();++i){
            string Head = str.substr(0,i);
            string Last = str.substr(i,str.length()-i);
            string newString = Head+*ic+Last;
            vStr.push_back(newString);
        }
    }
    //对每一个生成的字符串进行判断
    if(existHuiWenVector(vStr))
        cout<<"YES"<<endl;
    else
        cout<<"NO"<<endl;
 
    //for(vector<char>::iterator it = charVec.begin();it!=charVec.end();++it)
    //    cout<<*it;
    //for(vector<string>::iterator it=vStr.begin();it!=vStr.end();++it)
    //    cout<<*it<<endl;
    return 0;
}

/*************************************以下为朋友们的思路****************************************/

分析2（递归思路）：

    穷举法是生产所有的新字符串，然后对每一个字符串进行判断，然而加入一开始的输入字符串首尾字符就不相等，那么不论在中间如何插入字符生成新的字符串，都是非回文串，而这部分是穷举法会多余计算的。
    所以，可以根据判断输入字符串的首尾字符是否相等作为递归终止条件。若不相等，那么检测2种情况，将首字母添加于字符串后面，以及将尾字母添加到字符串前面时生成的2种新字符串，判断这2个字符串是否是回文串，若是则输出“YES”，否则输出“NO”。
   若一开始首尾字符相等，那么去掉首尾字符后的新字符串调用递归。

分析3（非递归思路）：
     回文串是以某个字符（奇数传）或某2个字符（偶数串）为中心，左右两边的字符相等的字符串。假如字符串有可能在加入一个字符后成为回文串，那么与加入的字符位置轴对称的另一个字符在源字符串中被删除掉得到的字符串也应该是回文串。
    所以，只要把尝试抽离每一个位置的字符后得到的新字符串，判断其是否是回文串就可以知道。问题最大规模为运算10次检测。


总结：递归思路和非递归思路的计算规模相当，都是最大为10次检测。


代码（C++实现）：
 

#include <iostream>
 
using namespace std;
 
bool isHuiWenString(const string &str)
{
    for(int i=0,j=str.length()-1;i<str.length()/2+1;i++,--j)
    {
        if(str[i]!=str[j])
            return false;
    }
    return true;
}
 
//递归方法
bool judgeString(const string& str)
{
    if(str[0] != str[str.length()-1]){
        string s1 = str[str.length()-1]+str;
        string s2 = str+str[0];
        if(isHuiWenString(s1) || isHuiWenString(s2))
            return true;
        return false;
    }
    else return judgeString(str.substr(1,str.length()-2));
}
 
//非递归方法
bool judgeString2(const string& str)
{
    for(int i=0;i<str.length();i++)
    {
        string Head = str.substr(0,i);
        string Last = str.substr(i+1,str.length()-i-1);
        string newString = Head+Last;
        if(isHuiWenString(newString))
            return true;
    }
    return false;
}
 
int main()
{
    string str;
    cin>>str;
    string resultStr;
   if(str.empty())
        resultStr="NO";
    //当str的长度小于等于2，或者str本身是回文串，那么一定可以成为回文串
    if(str.length() <= 2 || isHuiWenString(str))
        resultStr = "YES";
    //判断字符串，其中judgeString是递归方法，judgeString2是非递归方法
    if(judgeString(str))
        resultStr = "YES";
    else resultStr="NO";
    cout<<resultStr<<endl;
    return 0;
}