1047. Remove All Adjacent Duplicates In String

Leetcode link

题目简介

/**
 * @param {string} s
 * @return {string}
 */

题目给我们一个字符串 s

要求我们把 s 相邻的重复字符删除

最后返回剩余字符串

解题思路

我们使用一个栈 stack 来记录剩余字符

每次遍历新字符的时候，我们都用 stack 栈顶跟其比较，如果相同则让栈顶出栈，否则将当前元素如栈

最后我们把 stack 转换成字符串即可

Javascript

/**
 * @param {string} s
 * @return {string}
 */
var removeDuplicates = function (s) {
    const stack = [];

    for (let i = 0; i < s.length; i++) {
        if (stack.length === 0 || s[i] !== stack[stack.length - 1]) {
            stack.push(s[i]);
        } else {
            stack.pop();
        }
    }

    return stack.join("");
};

复杂度分析

时间

O(n)

空间

O(n)