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

xiaoxi666

发布于 2018-10-29 09:13:33

1.4K00

代码可运行

文章被收录于专栏：xiaoxi666的专栏xiaoxi666的专栏

运行总次数：0

代码可运行

题目描述

给定一个字符串，问是否能通过添加一个字母将其变为回文串。

输入描述

一行一个由小写字母构成的字符串，字符串长度小于等于10。

输出描述

输出答案(YES\NO).

示例

输入coco，输出YES.

思路

1.常规方法，先判断整体是否回文，若整体回文，可以在中间加一个数，直接返回YES。如果整体不是回文，依次去掉一个字符后判断剩下的字符串是否为回文串，时间复杂度O(n^2)。如abcddecba：1.去掉a，判断bcddecba；2.去掉b，判断acddecba；3.去掉c，判断abddecba；等等。一直进行下去，若发现回文即可停止返回YES，反之如果一直没发现回文串，返回NO。 2.创意解法，先找到不匹配的位置，然后提取出中间不匹配的的字符串，分别判断其去掉头和去掉尾的两个字符串是否为回文，其中一个为回文即可。时间复杂度O(n)。如abcddecba，取出dde，然后判断dd和de，发现其中有一个满足回文，即返回YES。反之返回NO。 3.扩展解法，先把原字符串逆序，然后计算两字符串的最长公共子序列长度，最后diff=字符串长度-最长公共子序列长度，diff即为如果可以形成回文串，原字符串需要添加的字符个数。用到这个题目里，如果diff<=1，即可。时间复杂度O(n^2)。可以看到，这种解法可以解决一类问题：添加几个字符可以构成回文串？

代码

方法一

 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 }