如何在Java中删除字符串中的相邻副本

我一直在寻找这个答案一段时间。我发现使用HashSet或LinkedHashSet删除重复的解决方案的数量，但他们都删除所有重复，我只寻找相邻的。 “ 说一个字符串是 ”ABBCDAABBBBBBBBOR“ 所需的结果应该是 ”ABCDABOR“，而不是 ”ABCDOR“ 难道这在O（n）为achived感谢如何在Java中删除字符串中的相邻副本

来源

2016-12-01 NotSure

我真的想看到Java的8 +正则表达式的例子... – Jay

肯定：？

StringBuilder sb = new StringBuilder(); 
char[] chars = text.toCharArray(); 
char previous = chars[0]; 
sb.append(chars[0]); 
for(int i = 1 ; i < chars.length ; i++) { 
    if(chars[i] != previous) { 
     sb.append(chars[i]); 
     previous = chars[i]; 
    } 
} 
String res = sb.toString();

来源

2016-12-01 18:04:31

O（n）的时间解决方案：

public String removeAdjacentDuplicates(String s) { 
    StringBuilder resultBuilder = new StringBuilder(); 
    char previous = s.charAt(0); 
    resultBuilder.append(previous); 
    for (int i = 1; i < s.length(); i++) { 
     char current = s.charAt(i); 
     if (previous != current) { 
      resultBuilder.append(current); 
      previous = current; 
     } 
    } 
    return resultBuilder.toString(); 
}

来源

2016-12-01 18:14:20 Default71721

O（n）的时间，是的，但O（n）的空间也。 StringBuilder resultBuilder的大小直接关系到String的大小。我看到使它成为O（1）空间的唯一实用方式是，如果重复数据删除的字符串从不存储;您在处理时必须输出它。只要该方法必须返回一个单独的重复数据删除字符串，那么您将需要与输入字符串的大小直接相关的额外存储空间。但是，如果输入是char数组，那么您可以重新使用传递的数组，但是所有的交换你会去O（n^2）的时间。空间与时间一如既往。 –

好点，但用于存储结果的空间在空间复杂度分析中几乎总是被忽略。 – Default71721

这种方法正是我会写的东西。我认为OP是指我看到这个问题的时间，在我看到它之前根本没有想到空间。我假设这个问题来自一名学生，并认为我们应该提供最准确的答案。该算法使用的空间随输入字符串中的字符数量线性增加，因此O（n）。 O（1）意味着算法使用的空间是恒定的;无论输入字符串的长度如何，它都会消耗相同的空间量。 –

我刚开始用流的工作如此忍受我...

public static String removeAdjacentDuplicates(String input) { 
    if (input.length() <= 1) { 
     return input; 
    } 

    StringBuilder sb = new StringBuilder(); 
    sb.append(input.charAt(0)); 

    IntStream.range(1, input.length()) 
     .mapToObj(i -> input.charAt(i) != input.charAt(i - 1) ? input.charAt(i) : "") 
     .forEach(sb::append); 

    return sb.toString(); 
}

，或者如果这你的风格，而不是StringBuilder的：

return input.charAt(0) + String.join("", 
    IntStream.range(1, input.length()) 
     .mapToObj(i -> input.charAt(i) != input.charAt(i - 1) ? 
      String.valueOf(input.charAt(i)) : "") 
     .toArray(size -> new String[size]));

来源

2016-12-01 18:31:08 gregbert

如何在Java中删除字符串中的相邻副本

回答

相关问题