常见编程题——回文串

1、题目：判断一个字符串是否为回文。

解析：前后扫描字符串时，如果一旦发现有一个位置的字符不相同，就肯定不是回文，如果遍历完都相同，就是回文。

#include<iostream>
#include<string>
using namespace std;
//循环的方式
bool huiwen(string str){
	int i=0,j=str.length()-1;
	while(i<j){
		if(str[i]!=str[j]) return false;
		i++;
		j--;
	}
	return true;
}

//递归的方式
bool ishuiwen(string str,int low, int high, int length)  
{  
    if (length == 0 || length == 1)  
        return true;  
    if (str[low] != str[high])  
        return false;  
    return ishuiwen(str,low+1, high-1,length-2);  
} 
int main(){
	string str;
	cin>>str;
	cout<<boolalpha<<huiwen(str)<<endl;//输出true或false
	cout<<boolalpha<<ishuiwen(str,0,str.length()-1,str.length())<<endl;

        //直接调用c++里的反转函数，回文串反转之后和原串相同

        string s=str;

	reverse(s.begin(),s.end());
	bool re=(s==str?true:false);
	cout<<re<<endl;

	cin.get();
	cin.get();
	return 0;
}

2、判断一个字符串能否通过添加一个字符变成回文串。

解析：有三种情况，原字符串就是回文串，可以变成回文串，直接在中间添加和中间字符相同的字符即可；缺少一个字符，可以变成回文串，直接添加缺少的这一个就可以；缺少多个字符串，不能变成回文串。所以就按照判断回文串的那种方法，找出一共缺少几个，大于2个就不能变成回文串。

#include <iostream>
#include <string>
using namespace std;
bool fun(string str) {
	int i=0,j=str.length()-1;  
    int count=0;  
    while(i<j)  
    {  
        if(str[i]==str[j])       
        {  
            i++;  
            j--;  
        }  
        else  
        {  
            if(str[i+1]==str[j]||str[i]==str[j-1]) //判断是前面缺少还是后面缺少字符  
            {  
                str[i+1]==str[j] ? i++: j-- ;  
                count++;  
            }  
            else  
            {  
                count=2;  //连着两个字符都不等的时候就可以确定不能变成回文串
                break;  
            }  
  
        }  
    }  
  if(count<=1) return true;//缺少的字符不大于1个的时候，可以变成回文
  else return false; 
}

int main() {
    bool res;
    string _str;
    getline(cin, _str);
    res = fun(_str);
    cout << res << endl;
    return 0;
}

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

const int MAX = 1001;
int MaxLen[MAX][MAX]; //最长公共子序列，动态规划求法

int maxLen(string s1, string s2){
	int len1=s1.length();
	int len2=s2.length();
	for(int i=0;i<=len1;i++){
		MaxLen[i][0]=0;
	}
	for(int i=0;i<=len2;i++){
		MaxLen[0][i]=0;
	}
	for(int i=1;i<=len1;i++){
		for(int j=1;j<=len2;j++){
			if(s1[i-1]==s2[j-1]) MaxLen[i][j]=MaxLen[i-1][j-1]+1;//如果连续就只有这一种情况
			else MaxLen[i][j]=max(MaxLen[i-1][j],MaxLen[i][j-1]);//不连续可以有下面这种选择
		}
	}
	return MaxLen[len1][len2];

}

int main(){
    string s;
    while (cin >> s){
        int length = s.size();
        if (length == 1){
            cout << 1 << endl;
            continue;
        }
        //利用回文串的特点
        string s2 = s;
        reverse(s2.begin(),s2.end());
        int max_length = maxLen(s, s2);
        cout << length - max_length << endl;
    }
    return 0;
}