You've successfully subscribed to The Daily Awesome
Great! Next, complete checkout for full access to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

1047. 删除字符串中的所有相邻重复项 - Remove All Adjacent Duplicates In String

. 2 min read

【栈】

给出由小写字母组成的字符串 S重复项删除操作会选择两个相邻且相同的字母,并删除它们。

在 S 上反复执行重复项删除操作,直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

Example:

示例:

输入:"abbaca"
输出:"ca"
解释:
例如,在 "abbaca" 中,我们可以删除 "bb" 由于两字母相邻且相同,这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca",其中又只有 "aa" 可以执行重复项删除操作,所以最后的字符串为 "ca"。

提示:

  1. 1 <= S.length <= 20000
  2. S 仅由小写英文字母组成。

Analysis

题目的关键在于删除重复项,因此重点在于找到所有重复项,包含因为删除而产生的重复项,因此可以使用栈实现。
每次添加时比较是否与栈顶元素相同

  • 若相同则删除栈顶元素且不插入
  • 若不相同则插入新元素

Solution 【栈】 ( 76ms)

执行用时 : 76 ms, 在Remove All Adjacent Duplicates In String的Java提交中击败了60.63% 的用户

内存消耗 : 37.5 MB, 在Remove All Adjacent Duplicates In String的Java提交中击败了100.00% 的用户

class Solution {
    public String removeDuplicates(String S) {
        /* 只需删除重复项即可,因此可以使用栈实现
         * 每次添加时比较是否与栈顶元素相同
         *   - 若相同则删除栈顶元素且不插入
         *   - 若不相同则插入新元素
         * 时间复杂度:O(N)
         * 空间复杂度:O(N)
         */
        char[] s = S.toCharArray();
        int len = s.length;
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < len; i++) {
            if (stack.isEmpty() || s[i] != stack.peek()) {
                stack.push(s[i]);
            } else {
                stack.pop(); 
            }
        }
        /* 数据的展示可以继续优化 */
        StringBuilder str = new StringBuilder();
        for (Character c : stack) {
            str.append(c);
        }
        return str.toString();
        
    }
}

复杂度分析

时间复杂度:O(N)
空间复杂度:O(N)