Topic describes

1047. Remove all adjacent duplicates from a string

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 <= S.length <= 20000 S The value consists of lowercase letters only.Copy the code

Link: leetcode-cn.com/problems/re…

Algorithm ideas

simulation

When we enumerate a number, we compare it with the number that still exists. If it is equal, we delete the two numbers.

In code, we can use a hash table to record the number that was deleted, iterate over it, and compare it to the last number that was not deleted. Iterate through the string one last time, noting down any characters that still exist.

The code is as follows:

/ * * *@param {string} S
 * @return {string}* /
var removeDuplicates = function(s) {
    const n = s.length
    const hash = {}
    for(let i = 1; i < n; ++ i) {
        let j = i - 1
        while(j >= 0 && hash[j]) -- j
        if(s[i] == s[j]) 
            hash[i] = hash[j] = true
    }
    let ans = ""
    for(let i = 0; i < n; ++ i)
        if(! hash[i]) ans += s[i]return ans;
};
Copy the code

Time complexity: O(n ^ 2)

The stack

Based on the above thinking, we can see that this is similar to a game of “elimination”, and if you read my articles often, you will see that every time there is a “elimination” property in the problem, it can be solved using the first-in, first-out feature of the stack.

The implementation process is like this: we maintain a stack to store the current undeleted characters, and then see if the next character is equal to the top of the stack, if so, we should remove the next character and the current top of the stack, we can pop the top of the stack.

The code is as follows:

/ * * *@param {string} S
 * @return {string}* /
Array.prototype.top = function() {
    return this[this.length - 1]}var removeDuplicates = function(s) {
    const n = s.length
    const stk = []
    for(let i = 0; i < n; ++ i) {
        if(stk.length && stk.top() === s[i]) stk.pop()
        else stk.push(s[i])        
    }
    return stk.join("")};Copy the code

Time complexity: O(n) Space complexity: O(n)

This article is participating in the “Gold Digging march Campaign”, click to see the details of the campaign