Topic describes

Leetcode link: 1047. Remove all adjacent duplicates in a string (easy)

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"In, we can delete"bb"Since the letters are adjacent and identical, this is the only duplicate item that can be deleted at this point. And then we get the string"aaca"And only one of them"aa"Deduplication can be performed, so the last string is"ca".Copy the code

Tip:

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

JavaScript template:

/ * * *@param {string} S
 * @return {string}* /
var removeDuplicates = function (S) {};Copy the code

Thought analysis

First, we can write directly according to the idea of the title, that is, recursive elimination of all adjacent characters of the same character.

The time complexity is O(n2), and each recursion is traversed once

The space complexity is O(n) for maintaining the recursive call stack

The specific code is as follows:

var removeDuplicates = function (S) {
  let temp = S[0];
  for (let i = 1; i < S.length; i++) {
    if (S[i] === temp) {
      return removeDuplicates(S.slice(0, i - 1).concat(S.slice(i + 1)));
    }
    temp = S[i];
  }
  return S;
};
Copy the code

To optimize the

Recursive calls are straightforward, but the downside is that they are too time intensive. So what can we do to reduce time complexity? We can maintain a stack and iterate through every character in the string, pushing it off the stack if it matches the top element, pushing it off the stack otherwise. Then concatenate the stack element and return.

The time complexity is O(n), and you only need to traverse the string once

The space complexity is O(n) and is used to maintain the stack

var removeDuplicates = function (S) {
  const stack = [];
  for (const char of S) {
    if (stack.length && stack[stack.length - 1] === char) {
      stack.pop();
    } else{ stack.push(char); }}return stack.join("");
};
Copy the code

To summarize

This problem can be solved by brute force at O(n2), but a better solution can be achieved by using a stack to reduce the time to O(n).

  • Let’s use JavaScript to brush algorithms: LeetCode-JavaScript

  • This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign