Source: LeetCode

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"
Copy the code

For example, in “abbaca”, we can delete “bb” because the letters are adjacent and identical, this is the only duplicate item that can be deleted at this point. Then we get the string “aaca”, where only “aa” can be deduplicated, so the final string is “ca”.

Tip:

  • 1 <= S.length <= 20000
  • The “S” is a lowercase letter only.

Method 1: Leverage the stack

  • Put a single characterpushInto the stack
  • Check whether the character is equal to the element at the top of the stack
  • If so, delete the top element of the stack; Otherwise the characterpushInto the stack
  • Finally, the element is removed from the stack

var removeDuplicates = function(S) {
    let arrS = []
    for (let i = 0; i < S.length; i++) {
        // Check whether it is equal
        if (arrS[arrS.length - 1] === S[i]) {
            arrS.pop()
        } else {
            arrS.push(S[i])
        }
    }
    return arrS.join(' ')};Copy the code

Method 2: Convert a string to an array

  • Determines whether each element in the array is equal to the previous element
  • If they are equal, delete the two elements and move the index one bit forward

Note: delete characters. The number of strings changes, so be aware of index changes

var removeDuplicates = function(S) {
    S = S.split(' ')
    for (let i = 1; i < S.length; i++) {
        if (S[i] === S[i - 1]) {
            // Remove two identical characters
            S.splice(i - 1.2);
            // If the first two are the same, I =0, because above I ++, then return to the second value
            if (i < 2) {
                i = 0
                // Go back to the previous one to start the comparison
            } else {
                i = i-2}}}return S.join(' ')};Copy the code