java - java中如何减少给定字符串中的字符直到它变成回文

Question

这里我有代码来检查给定的字符串是否是回文，但不知道从最后一个字符开始减少字符的过程。要更改字符，我需要遵循以下规则:例如 String input="abcde"。字母“e”可以转换为“d”，但如果字符变成“a”，则不能将“e”转换为“d”，我们无法进一步更改。这是我的代码:

 public static void main(String[] args) {
    String input = "abcd";
    String temp = input;
    String output = "";
    for (int i = output.length() - 1; i >= 0; i--) {
        output = output + output.charAt(i);
    }
    if(temp.equals(output)){
        System.out.println("String is palindrome");
    }else{
        System.out.println("Not a palindrome");
    }
}

输出顺序逻辑如下:

if input is =abcd
    abcc('d' converted to 'c')and check for palindrome
    abcb('c' converted to 'b')and check for palindrome
    abca('b' converted to 'a')and check for palindrome
    abba('a' further we can't change so shift to previous letter 'c' and change to 'b') 
          and check for palindrome

String is palindrome and count is=4

if input=cbdf
    cbde('f' converted to 'f')and check for palindrome
    cdbd('e' converted to 'd')and check for palindrome
    cdbc('d' converted to 'c')and check for palindrome
    cdbb('c' converted to 'b')and check for palindrome
    cdba('b' converted to 'a')and check for palindrome
    cdaa('a' further we can't change so shift to previous letter 'b' and change to 'a')
      and check for palindrome
    ccaa('a' further we can't change so shift to previous letter 'd' and change to 'c')
      and check for palindrome
    cbaa('c' converted to 'b')and check for palindrome
    caaa('a' further we can't change so shift to previous letter 'c' and change to 'b')
       and check for palindrome
    baaa('b' converted to 'a')and check for palindrome
    aaaa now string is palindrome
    String is palindrome and count is=10
   finally i need the count to make string palindrome.

Answer 1

假设我理解你的问题，那么你解决这个问题的方式效率很低。我将这样做:

String toPalindrome(String str){
    StringBuilder reverse = new StringBuilder(str).reverse();

    for(int idx = 0; idx < str.size()/2; idx++)
        if(str.getCharAt(idx) < reverse.getCharAt(idx))
            reverse.setCharAt(idx, str.getCharAt(idx));

    return reverse.subString(0,str.size()/2) + reverse.reverse().subString(str.size()/2);
}

除了此代码中的差一错误之外，这应该可以产生您需要的输出。

使用这种方法，我们不必逐个递减每个字符 - 我们只需立即用目标值替换每个字符。我们也永远不必检查它是否是回文，因为该方法保证产生一个回文(毕竟，它在返回步骤中将一个字符串与其镜像连接起来)。

编辑:看到我们只需要返回字符被减少的次数，我们可以做一些更简单的事情:

int abs(int x){
    return x>0?x:-x;
}

int palindromeCounts(String str){
    int count = 0;

    for(int idx = 0; idx < str.length()/2; idx++)
        count += abs(str.charAt(idx) - reverse.charAt(str.length()-1-idx));

    return count;
}