如何使用递归删除连续的重复项？

Question

我需要使用递归方法从字符串中删除连续的重复项（例如，将 "aabbcddeghhi" 转换为 "abcdefghi."）到目前为止我已经做到了。

如果我有注释的 removeDuplicates() 行，我会得到一个奇怪的数字输出和这个异常：

a195b197199d201203205207h209Exception in thread "main" java.lang.StringIndexOutOfBoundsException: String index out of range: 13

如果我注释掉该行，它只会打印：

这是我的代码：

package recursion;

public class recursion {

    public static void main(String[] args){
        removeDuplicates("aabbcddefghhi", 0, 1);
    }

    public static void removeDuplicates(String a, int b, int c){
        if (a.length() <= 1){
            System.out.print(a.charAt(b));
        }
        else if (a.charAt(b) == a.charAt(c)){
            System.out.print(a.charAt(c));
            b++;
            c++;
            //removeDuplicates(a,b,c);
        }
        else if (a.charAt(b) != a.charAt(c)){
            System.out.print(a.charAt(b) + a.charAt(c));
            b++;
            c++;
            removeDuplicates(a,b,c);
        }
        else{
            System.out.print("");
            b++;
            c++;
            removeDuplicates(a,b,c);
        }
    }
}

Answer 1

这段代码有一些问题：

您没有终止递归的好方法。您实际上并没有减小字符串的大小，因此您的初始结束条件将不起作用。
根据您在此处使用的逻辑，您无法打印字符串的最后一个字符。
你的最终 if 条件永远不会发生
您永远不想将两个字符加在一起。在这种情况下，您也不想打印这两个字符。
如果两个字符匹配，您不想打印一个字符，因为您不知道还会有多少个字符。
您不需要 c 值，它始终等于 b+1，只需使用一个数字即可。

下面是包含所有这些更改的结果代码：

public static void main(String[] args) {
  removeDuplicates("a");
  System.out.println();
  removeDuplicates("aabbcdddefghhii");
  System.out.println();
  removeDuplicates("aabbcdefa");
}

public static void removeDuplicates(String a) {
   removeDuplicatesHelper(a, 0);
}

public static void removeDuplicatesHelper(String a, int b) {
  if (b == a.length() - 1) {
    System.out.print(a.charAt(b));
  } else if (a.charAt(b) == a.charAt(b+1)) {
    b++;
    removeDuplicatesHelper(a, b);
  } else {
    System.out.print(a.charAt(b));
    b++;
    removeDuplicatesHelper(a, b);
  }
}

输出：

a
abcdefghi
abcdefa

Answer 2

 public static String duplicates(String word, char curr) {

    if (word.length() == 0) return "";

    char next = word.charAt(0);

    if (word.length() == 1) {
       return curr == next ? "" : word;
    }

    if (curr != next) {
         return next + duplicates(word.substring(1), next);
    }
    else {
        return duplicates(word.substring(1), curr);
    }
 }

呼叫为：

public static void main(String[] args) {
    System.out.println(duplicates("aabbbbbb976fkkkkc", '[=11=]'));
}

如何使用递归删除连续的重复项？

How can I remove consecutive duplicates using recursion?

java

recursion

duplicate-removal