Рекурсивно удалить все соседние дубликаты

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 
} 

Все, что осталось в стеке, является результирующей строкой.

Добавочный вход пространство: O (п) Сложность: O (п)

Является ли это правильным решением и canyone объяснить о (п) решение поясняется в сообщении?

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, мы, безусловно, выскакивают элемент отключения стека A и, следовательно, размер стека A уменьшается на 1 после каждого шага 3 .

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).

Sidenote - Всякий раз, когда вы думаете о рекурсии, его всегда легче думать о нем, как о глубине вызова функций, а затем возвращать значения, которые затем собираются, чтобы вернуть окончательный результат.

В любом случае, я надеюсь, что смогу прояснить себя и надеюсь, что это поможет вам начать работу в правильном направлении.

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); 
     } 


    }