在 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" -> 假
"d" + "abcd" -> "dabcd" -> 假
"dc" + "abcd" -> "dcabcd" -> 假
"dcb" + "abcd" -> "dcbabcd" -> 真，终止

这是一个固定版本：

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

IDEONE：http://ideone.com/tawjmG

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

求中点，从0循环到中点，length-1到中点。

如果回文，return

如果不是回文，中点加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 3

我不确定我是否理解这个问题，但根据我的理解，您想将 Hello 之类的字符串转换为 olleHello 来执行此操作，循环遍历字符串的每个字符，如：

    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 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))

在 Java 中将字符串转换为回文

Converting a string into a palindrome in Java

java

string

palindrome