将字符串转换为Java回文

Question

我正在尝试通过在S前面添加0个或多个字符来找到一个可以从S创建的最短回文。例如，最短回文可以从“ baaa”构建为“ aaabaaa”。下面给出了我正在使用的两个函数。这对于这种情况有效，因为在所有情况下都不会产生最短的结果。

public static boolean checkPalindrome(String s){

        for (int i = 0; i < s.length()/2; i++) {
            if (s.charAt(i) != s.charAt(s.length() - i - 1)) return false;
        }

        return true;

    }

    public static int makePalindrome(String s){
    int min = 0;
    StringBuilder str = new StringBuilder(s);
    for (int i = 1; i < s.length() ; i++) {
        str.insert(0, s.charAt(i));
        if (checkPalindrome(str.toString()) == true) {
            min = str.length();
            break;
        }

    }
    return min;
}

我似乎无法弄清楚我缺少什么逻辑步骤。

Answer 1

您的辅助方法checkPalindrome似乎正确。您的想法也是正确的（将字符附加到回文，直到结果回文为止），但是您的处理方法是错误的。

要重申：我们的逻辑是，虽然我们的结果不是回文，但从末尾（移至字符串的开头）取下一个字符并将其附加到前缀。因此，对于字符串"abcd"，我们可以尝试

• "" + "abcd"-> "abcd"-> false
• "d" + "abcd"-> "dabcd"-> false
• "dc" + "abcd"-> "dcabcd"-> false
• ["dcb" + "abcd"-> "dcbabcd"-> true，终止

这里是固定版本：

public static String makePalindrome(String base){
    String pref = "";
    int i = base.length() - 1;
    while(! checkPalindrome(pref + base)){
        pref = pref + base.charAt(i);
        i --;
    }
    return pref + base;
}

Answer 2

我不确定我是否理解这个问题，但是根据我的理解，您想将像Hello这样的字符串转换为olleHello，为此，请使用like循环遍历字符串的每个字符：

    String example = "Hello There Mate"; //our string
    StringBuilder exampleBuilder = new StringBuilder();
    for(int i=example.length()-1; i>0; i--)
        exampleBuilder.append(example.charAt(i));
    //Our loop, the reason why it is example.lenght-1
    //is because we want the first letter to appear only
    //1 time :)
    String finalString = exampleBuilder.toString()+example;
    //The final string, should be 'olleHello'
    System.out.println(finalString);

希望这就是您想要的：D

Answer 3

IDEONE：http://ideone.com/tawjmG

我们可以使用以下逻辑找到最短的回文：

找到中点，从0到中点，从长度1到中点循环。

如果回文，请返回

如果不是回文，请在中点加1，执行相同的逻辑

使用代码：

static String shortestPalindrome(String s) {
    if (s.length() == 1) return s;
    return recShortestPalindrome(s, s.length()>>1, 0);
}

static String recShortestPalindrome(String s, int mid, int add) {
    // AABBA[X]
    int fakeLen = s.length() + add;
    for (int i = 0; i < mid; i++) {
        char c1 = s.charAt(i);
        int p1 = fakeLen - 1 - i;

        if (p1 < s.length()) {
            char c2 = s.charAt(p1);

            if (c2 != c1) {
                return recShortestPalindrome(s, mid+1, add+1);
            }
        }
    }

    // found a pattern that works
    String h1 = s.substring(0, mid);
    String h2 = new StringBuilder(h1).reverse().toString();

    String ret = h1+h2;

    int midPoint = ret.length()/2;

    if (ret.length()%2 == 0 && ret.length() >= 2) {
        char c1 = ret.charAt(midPoint);
        char c2 = ret.charAt(midPoint-1);

        if (c1 == c2) {
            return ret.substring(0, midPoint) + ret.substring(midPoint+1, ret.length());
        }
    }

    return h1+h2;
}

Answer 4

Python解决方案：

def isPalindrome(x):
    if x == "":
        return False

    r = ""
    r = str(x)
    r = r[::-1]

    return True if x == r else False

def makePalindrome(my_str):

    pref = ""
    i = len(my_str) - 1

    while isPalindrome(pref + my_str) == False:
        pref = pref + my_str[i]
        i -= 1

    return pref + my_str







my_str = "abcd"
print(makePalindrome(my_str))