1047. 删除字符串中的所有相邻重复项

leetcode链接：
https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/

题目分析

将字符串从头开始，一步步放入栈中，先判断其是否和栈顶的字符串相等，如果相等则弹出栈，如果不等，则放入栈中。

方案一

class Solution {
    public String removeDuplicates(String s) {
        Deque deque = new LinkedList<Character>();

        for (int i = 0; i < s.length(); i++) {
            if (!deque.isEmpty() && ((Character) deque.peek()) == s.charAt(i)) {
                deque.pop();
            } else {
                deque.push(s.charAt(i));
            }
        }

        StringBuffer result = new StringBuffer();

        while (!deque.isEmpty()) {
            result.append((Character) deque.pollLast());
        }

        return result.toString();
    }
}

结果

解答成功:
执行耗时:34 ms,击败了59.74% 的Java用户
内存消耗:43.3 MB,击败了51.18% 的Java用户

分析

时间复杂度：
O( n )

空间复杂度：
O( n )

官方题解

https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/solution/shan-chu-zi-fu-chuan-zhong-de-suo-you-xi-4ohr/

class Solution {
    public String removeDuplicates(String s) {
        StringBuffer stack = new StringBuffer();
        int top = -1;
        for (int i = 0; i < s.length(); ++i) {
            char ch = s.charAt(i);
            if (top >= 0 && stack.charAt(top) == ch) {
                stack.deleteCharAt(top);
                --top;
            } else {
                stack.append(ch);
                ++top;
            }
        }
        return stack.toString();
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/solution/shan-chu-zi-fu-chuan-zhong-de-suo-you-xi-4ohr/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。