给定一个字符串，问是否能通过添加一个字母将其变为回文串（三种思路）

 1 #include <iostream>
 2 
 3 #include <string>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 //判断回文方法1
 8 bool IsHuiWen(string str)
 9 {
10     string rstr=str;
11     reverse(rstr.begin(),rstr.end());
12     return str==rstr;
13 }
14 
15 int main(){
16     string str;
17     while(cin>>str){
18         bool flag=false;
19         for(int i=0;i<(int)str.size();++i){
20             if(IsHuiWen(str.substr(0,i)+str.substr(i+1,str.size()-1-i))){
21                 flag=true;
22                 break;
23             }
24         }
25         cout<< ((flag==true) ? "YES" : "NO")<<endl;
26     }
27     return 0;
28 }

 1 #include <iostream>
 2 
 3 #include <string>
 4 #include <algorithm>  //std::reverse
 5 using namespace std;
 6 
 7 //判断回文方法1
 8 //bool IsHuiWen(string str)
 9 //{
10 //    string rstr=str;
11 //    reverse(rstr.begin(),rstr.end());
12 //    return str==rstr;
13 //}
14 
15 //判断回文方法2
16 bool IsHuiWen(string str)
17 {
18     for(int i = 0; i<(int)str.size()/2;i++){
19         if(str[i] != str[str.size()-1-i])
20             return false;
21     }
22     return true;
23 }
24 
25 int main()
26 {
27     string str;
28     while(cin>>str)
29     {
30         bool flag = false;
31         int i;
32         for(i = 0; i<(int)str.size()/2;i++)
33         {
34             if(str[i] != str[str.size()-1-i])
35                 break;;
36         }
37         if(i == (int)str.size()/2)
38             flag = true;
39         else
40             flag = (IsHuiWen(str.substr(i+1,str.size()-2*i-1)) || IsHuiWen(str.substr(i,str.size()-2*i-1)));
41 
42         cout<< ((flag==true) ? "YES" : "NO")<<endl;
43     };
44     return 0;
45 }

 1 #include <iostream>
 2 #include <vector>
 3 #include <string>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 int findLCS(string str1,string str2) {
 8     // write code here
 9     if(0 == str1.size() || 0 == str2.size())
10         return 0;
11     vector<vector<int> > array(str1.size()+1,vector<int>(str2.size()+1,0));
12     for(size_t i=1; i<= str1.size(); ++i){//注意：是小于等于
13         for(size_t j=1; j<= str2.size(); ++j){//注意：是小于等于
14             if(str1[i-1] == str2[j-1]){//前面填充了一行一列，因此判断i-1和j-1
15                 array[i][j]=array[i-1][j-1]+1;
16                 }
17             else
18                 array[i][j]=max(array[i-1][j],array[i][j-1]);
19         }
20     }
21     return array[str1.size()][str2.size()];
22 }
23 
24 int main(){
25     string str;
26     while(cin>>str){
27         string rstr=str;
28         reverse(rstr.begin(),rstr.end());
29         int diff=(int)str.size()-findLCS(str,rstr);
30         cout<<(diff<2?"YES":"NO")<<endl;
31     }
32     return 0;
33 }