如何在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中刪除字符串中的相鄰副本

回答

相關問題