递归删除所有相邻的重复项 [英] Recursively remove all adjacent duplicates

问题描述

找到一种算法，递归地删除给定字符串中的所有相邻重复项这是原始问题.我想到了一种使用堆栈的算法.

Find an algorithm to recursively remove all adjacent duplicates in a given string this is the original question.I have thought of an algorithm using stacks.

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
}

堆栈上剩下的就是字符串.

Whatever is remaining on stack is the resultant string.

辅助空间:O(n)复杂度:O(n)

Auxillary space :O(n) Complexity : O(n)

这是正确的解决方案吗，canyone可以解释帖子中解释的o(n)解决方案吗?

Is this a correct solution and canyone explain the o(n) solution explained in the post?

推荐答案

这是正确的解决方法

Is this a correct solution

是的.考虑到@rici提到的内容，让我尝试消除您使用堆栈的想法.

Yes it is. Let me try to sanitize your idea of using stacks taking into account what @rici mentioned.

您想遍历字符串一次的字符.这就是算法的流程:

You want to traverse through the characters of the string once. This is how your algorithm flows:

 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中弹出一个元素，因此，在每个步骤3之后，堆栈A的大小将减小1.

The above algorithm is clearly O(N) because at every step 3, we are definitely popping an element off Stack A and therefore the size of Stack A goes down by 1 after every step 3.

可以解释帖子中解释的o(n)解决方案吗?

canyone explain the o(n) solution explained in the post?

来到您想要的递归算法等一下就是这样:

Coming to the recursive algorithm that you wanted to get a hang on. This is how it goes:

在任何时间点，函数 removeUtil 具有两个值-一个是字符数组 str 从中我们必须删除相邻的重复项，另一个是字符 last_removed .

At any point in time the function removeUtil has two values - one is the character array str from which we have to remove adjacent duplicates and the other is the character last_removed.

带有一些描述的伪代码-

Pseudo code with some description -

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

And here also since we are traversing the character array and 'forming' the final character array that get returned by appropriately appending and removing characters, the time complexity is O(N).

Sidenote -每当考虑递归时，总会更容易想到它，就像深度函数调用展开一样，然后返回值，然后将这些值收集起来以返回最终结果.

Sidenote- Whenever thinking about recursion, its always easier to think of it like a depth of function calls unfolding and then returning values which then get collected to return the final result.

无论如何，我希望我能澄清自己，并希望这可以使您朝正确的方向开始.

Anyway, I hope I could clarify myself and hope this gets you started in the right direction.

这篇关于递归删除所有相邻的重复项的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！