java - 如何递归删除所有相邻的重复项

Question

我无法想出最佳解决方案( O(n) 时间)来递归地从字符串中删除相邻的重复项。我的尝试:

public static String removeDuplicate(String s) {
   if ( s == null ) return null;
   if ( s.length() <= 1 ) return s;
   if( s.substring(1,2).equals(s.substring(0,1))) 
      return removeDuplicate(s.substring(1));
   else return s.substring(0,1) + removeDuplicate(s.substring(1));
}

但它不适用于以下情况:

 "azxxzy" -> "ay"

在上面的例子中，这些是字符串转换:

阿西西兹疯狂的哎呀

示例输入输出:

输入:azxxzy 输出:ay

输入:caaabbbaacdddd 输出:空字符串

输入:acaaabbbacdddd 输出:acac

更新

我在下面发布了一个版本的答案。

Answer 1

正如您问题评论中的人所提到的，String 操作已经是 O(n)，因为 String 是不可变的。这可以通过使用 Character 数组来解决。由于您还要删除内容，因此您还应该在该数组中使用 null 以防止每次删除字符时都必须四处移动内容。最后，您需要额外传递数组以将其转换为字符串。

你问的真正问题更简单。从像azxxzy这样的字符串中删除xx 会将xx 前后的字符放在一起，它们可能是相同的。所以只需再次检查一下:将光标放在前面一个位置。继续使用字符串 zzy 而不是 zy。

复杂度将保持为 O(n)，因为每个字符最多检查两次并且最多可以删除一次。

由于您专门要求递归答案，我假设这是一个家庭作业练习并将实现留给您(使用 Character 数组并添加起始位置的索引作为额外参数到你的方法)。非递归算法会更有效，也更容易实现!