遞歸刪除所有相鄰的重複項

Question

找到一個算法到recursively remove all adjacent duplicates in a given string這是原始問題。我想到了一個使用堆棧的算法。

1.Initialize a stack and a char_popped variable 
2.Push the first char of str into the stack. 
3.now iterate through the characters of string. 
if the top of stack matches with the character 
{ 
pop the character from the stack, 
char_popped=character 
} 
else 
{ 
    if(character==char_popped) 
     {DONT DO ANYTHING} 
    else 
     push the character on the stack 
     char_popped=null 
} 

不管剩下的堆棧是結果字符串。

Auxillary空間：O（n）的複雜度：O（N）

這是一個正確的解決方案和canyone解釋O（N）解決方案在後解釋呢？

Answer 1

這是一個正確的解決方案

是的。讓我試着清理使用堆棧的想法，並考慮@rici提到的內容。

您想遍歷字符串的字符一次。這是你的算法是如何流動的：

1. Initialize a stack containing the string. (Stack A) 
2. Pop top most element of Stack A and push into Stack B thereby initializing Stack B 
3. Pop from Stack B and pop from Stack A and check if they are equal. 
4. If they aren't push both the elements in Stack B. (The popped element from Stack A is pushed later to preserve order) 
5. Do step 3 till Stack A is empty. 

Stack B should contain the chracters with adjacent duplicates removed. 

上述算法顯然是O(N)，因爲在每一個步驟3，我們肯定是突然離開棧中的一個元素，因此棧中的大小每一個步驟3後下降了1

canyone解釋了o（n）解決方案中的解釋？

即將到達recursive algorithm，你想掛起。這是怎麼一回事呢：

在任意時間點的功能removeUtil有兩個值 - 一個是字符數組str 從中我們必須刪除相鄰的重複，另一個是字符last_removed。

僞一些描述碼 -

1. It checks if the first two characters of the str are same, if they are: 
    update last_removed and call removeUtil again on the remaining characters 
    (hence the str ++) 

2. If first two characters are not same, we do the same exercise as in 1 
    only this time we start from str[1], hence removeUtil(str+1, last_removed); 

3. Now the returned value from call in 2 is stored in a rem_str because we have 
    characters that didn't match like str[0] in 2 that are orphan and need to be appended 
    in the final array just like we pushed elements into the stack in your case. 

4. Let's assume the string is 'abbac'- 

    In the first call we reach here -> removeUtil("bbac", '\0'); 
    str[0] -> 'a' 

    Now this call -> removeUtil("bbac", '\0'); returns "ac" 
    and when the recursion unfolds at this point rem_str -> "ac" 
    str[0] -> 'a' 

    Hence this : 
    if (rem_str[0] && rem_str[0] == str[0]) 
    { 
    *last_removed = str[0]; 
    return (rem_str+1); // In our case this would return "c" to the previous function call 
    } 

5. if (rem_str[0] == '\0' && *last_removed == str[0]) 
    return rem_str; 

    Consider the string they mention -> "acbbcddc" 
    So at some point we have situation where: 
    this call happens-> removeUtil("bbcddc", '\0'); 
    followed by -> removeUtil("cddc", 'b'); 
    followed by -> removeUtil("ddc", 'b'); 
    followed by -> removeUtil("c", 'd'); 
    That returns 'c' and considering the str[0] in the string "cddc" , it goes to case 4 
    and therefore 'c' gets removed returning an empty string and last_removed -> 'c'. 

    So removeUtil("bbcddc", '\0'); returns an empty string with last_removed -> 'c'. 

    However, here str[0] is the same as the last_removed character and therefore should be removed. 


6. If none of the following string matches that means str[0] should be appended to final answer. 
    rem_str--; 
    rem_str[0] = str[0]; 
    return rem_str; 

而且這裏也因爲我們遍歷字符數組和「成形」是那些獲得通過適當追加和刪除字符返回的最後一個字符數組，時間複雜度爲O(N)。

旁註 - 每當想到遞歸時，總會更容易想到它，就像函數深度調用unfolding，然後返回值，然後收集它們以返回最終結果。

無論如何，我希望我能澄清一下自己，希望這能讓你開始朝正確的方向發展。

Answer 2

檢查這一項：

Scanner scanner = new Scanner(System.in); 
String str = scanner.next(); 
for (int i = 1; i < str.length(); i++) 
{ 
    if (str.charAt(i) == str.charAt(i-1)) 
    { 
     str = str.substring(0, i-1) + str.substring(i+1); 
     i = 0; 
    } 
} 
if (str.length() == 0) { 
    System.out.println("Empty String"); 
} else {    
    System.out.println (str); 
} 

Answer 3

package tryout.examples; 

import java.util.Scanner; 

public class RemovingAdjacentCharacterUsingStack 
{ 
    public static void main(String[] args) 
    { 
     Scanner in =new Scanner(System.in); 
     String str=in.next(); 

     CharStack cs=new CharStack(10); 

     char [] arr=str.toCharArray(); 

     for(int i=0;i<arr.length;i++) 
     { 
      if(i==0 || cs.top==-1) 
      { 
       cs.push(arr[i]); 
      } 
      else 
      { 
       if(cs.peek()==arr[i]) 
       { 
        cs.pop(); 
       } 
       else 
       { 
        cs.push(arr[i]); 
       } 
      } 

     } 
     System.out.println("after removing adjacent same characters-->"); 
     cs.display(); 

    } 
} 

    class CharStack 
    { 
     private char[] finalCharArray; 
     public int top; 


     public CharStack(int capacity) 
     { 
      top = -1; 
      finalCharArray=new char[capacity]; 
     } 

     public void push(char element) 
     { 
      finalCharArray[++top]=element; 
     } 

     public char pop() 
     { 
      return finalCharArray[top--]; 
     } 

     public void display() 
     { 
      for(int i=0;i<=top;i++) 
      { 
       System.out.println(finalCharArray[i]); 
      } 
     } 

     public char peek() 
     { 
      return finalCharArray[top]; 
     } 

     public boolean isEmpty() { 
      return (top == -1); 
     } 


    }