[编程题]添加回文串

添加回文串

对于一个字符串，我们想通过添加字符的方式使得新的字符串整体变成回文串，但是只能在原串的结尾添加字符，请返回在结尾添加的最短字符串。

给定原字符串A及它的长度n，请返回添加的字符串。保证原串不是回文串。
测试样例：

"ab",2

返回："a"

方法一：

1. 因为在原串结尾添加字符可以使其变成回文串，所以在原串开始位置删除字符也可以让其变成回文串;
2. 于是要删除的字符串与要添加的字符串互为回文；

import java.util.*;

public class Palindrome {
    public String addToPalindrome(String A, int n) {
        for(int i = 1; i < n; i++){
            String st = A.substring(i, n);
            if(st.equals(new StringBuffer(st).reverse().toString()))
                return (new StringBuffer(A.substring(0, i)).reverse().toString());
        }
        return A;
    }
}

Python版：

# -*- coding:utf-8 -*-

class Palindrome:
    def addToPalindrome(self, A, n):
        for i in range(1, len(A)):
            if A[i:n] == A[i:n][::-1]:
                return A[:i][::-1]
        return A

方法二：

1. 找出原串中的最长回文串（因为是在末尾添加使其变成回文串，所以最长回文字串一定是从前面某个位置开始到末尾位置）；
2. 剩余的字符串就与原串末尾要添加的字符串互为回文；

import java.util.*;

public class Palindrome {
    public String addToPalindrome(String A, int n) {
        String rsd = new StringBuffer(A).reverse().toString();
        for(int i = 0; i < n; i++){
            String s1 = A.substring(i, n);
            String s2 = rsd.substring(0, n - i);
            if(s1.equals(s2)){
                return rsd.substring(n - i, n);
            }
        }
        return A;
    }
}

其实方法一和方法二是一样的，但思考的切入点有一点点不同