题目:对于一个字符串,我们想通过添加字符的方式使得新的字符串整体变成回文串,但是只能在原串的结尾添加字符,请返回在结尾添加的最短字符串。给定原字符串A及它的长度n,请返回添加的字符串。保证原串不是回文串。"ab",2 返回:"a"
思路:刚开始思路很死,就是判断对称轴在哪,(对称轴一定在字符串右半边),如果对称轴的左右相同,那么分别再向左右继续判断相等,如果右边到达最后,那么这个对称轴成立,反之继续找对称轴,如果找不到,那么对称轴就是字符串最右边一个字符的右边,比如“abcd”,对称轴就是d后面,也就需要添加整个转置的字符串。。。但是对称轴有两种情况,一种是字符,比如"aba",‘b就是对称轴’;还有一种是空的,比如“abba”,对称轴在两个b中间。这两种情况都是一个做法,就是我刚才说的,但是都要判断。
public String addToPalindrome(String A, int n) {
if(n==2) return String.valueOf(A.charAt(0));
String res="";
int index=0;
boolean flag=false;
for(int i=n/2;i<n-1;i++){
//对称轴是字符,A[i]
if(A.charAt(i-1)==A.charAt(i+1)){
int l=i-1,r=i+1;
if(r==n-1){
for(int j=i-2;j>=0;j--)
res+=A.charAt(j);
return res;
}
while(A.charAt(l)==A.charAt(r)){
if(r==n-1){
flag=true;
index=l-1;
break;
}
l--;
r++;
}
}
if(flag){
for(int j=index;j>=0;j--)
res+=A.charAt(j);
return res;
}
//对称轴是A[i]和A[i+1]中间
if(A.charAt(i)==A.charAt(i+1)){
int l=i,r=i+1;
if(r==n-1){
for(int j=l-1;j>=0;j--)
res+=A.charAt(j);
return res;
}
while(A.charAt(l)==A.charAt(r)){
if(r==n-1){
flag=true;
index=l-1;
break;
}
l--;
r++;
}
}
if(flag){
for(int j=index;j>=0;j--)
res+=A.charAt(j);
return res;
}
//找不到对称轴的情况
for(int j=n-1;j>=0;j--)
res+=A.charAt(j);
return res;
}
看到一个简单点的方法,就是每次删除第一个字符,将此字符放入新串,判断剩下的是否回文,如果是,那么转置新串即为所求。
class Palindrome {
bool judge(string str){
string tmp = str;
reverse(tmp.begin(), tmp.end());
return tmp==str;
}
public:
string addToPalindrome(string str, int n) {
reverse(str.begin(), str.end());
string ans;
while (!str.empty()) {
ans.push_back(str.back());
str.pop_back();
if(judge(str))
break;
}
reverse(ans.begin(), ans.end());
return ans;
}
};