java - 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;
}