Delete all adjacent duplicates in a string

Title description:

Given a string S consisting of lowercase letters, the deduplication operation selects two adjacent and identical letters and deletes them.

The deduplication operation is repeated on S until the deletion cannot continue.

Returns the final string after all deduplication operations have been completed. The answer is guaranteed to be unique.

Example:
Input: "abbaca" Output: "ca" Explanation: For example, in "abbaca", we can delete "bb" because the two letters are adjacent and identical, this is the only duplicate item that can be deleted at this time. Then we get the string "aaca", where only "aa" can be deduplicated, so the final string is "ca".Copy the code
Tip:
1. 1 <= S.length <= 20000 2.Copy the code

Directions: For this part,

The general idea for deleting duplicate items is double pointer, the same for this problem we can use double pointer idea to solve, used to determine whether two characters are the same, but today I want to talk about how to use stack to solve this problem.

According to the prompt of the question, we can analyze the following contents:

  1. Multiple groups of adjacent duplicates, no matter which one we delete first, will not affect the final result.
  2. Deleting the current item requires comparison with the previous item, so we need a temporary stack to store the previous content.
  3. The current item is the same as the top of the stack. If inconsistent, push into the stack for subsequent use
  4. Finally, turn the remaining characters in the stack into strings.

Let’s look at the solution implementation:

Code implementation:

func removeDuplicates(s string) string {
    stack := []byte{}
    for i := range s {
        if len(stack) > 0 && stack[len(stack)-1] == s[i] {
            stack = stack[:len(stack)-1]
        } else {
            stack = append(stack, s[i])
        }
    }
    return string(stack)
Copy the code

Conclusion:

This question is not difficult, after the total feeling that this question is designed for the stack structure, but also to deepen the understanding of the stack.