我无法想出最佳解决方案( 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
更新
我在下面发布了一个版本的答案。
最佳答案
正如您问题评论中的人所提到的，String 操作已经是 O(n)，因为 String 是不可变的。这可以通过使用 Character 数组来解决。由于您还要删除内容，因此您还应该在该数组中使用 null 以防止每次删除字符时都必须四处移动内容。最后，您需要额外传递数组以将其转换为字符串。
你问的真正问题更简单。从像azxxzy这样的字符串中删除xx 会将xx 前后的字符放在一起，它们可能是相同的。所以只需再次检查一下:将光标放在前面一个位置。继续使用字符串 zzy 而不是 zy。
复杂度将保持为 O(n)，因为每个字符最多检查两次并且最多可以删除一次。
由于您专门要求递归答案，我假设这是一个家庭作业练习并将实现留给您(使用 Character 数组并添加起始位置的索引作为额外参数到你的方法)。非递归算法会更有效，也更容易实现!
关于java - 如何递归删除所有相邻的重复项，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/22211521/