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

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

难度简单166

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

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

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

示例：

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

提示：

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

栈

• 如果栈为空，向栈中加入当前的元素
• 如果栈不为空，判断栈顶元素和当前的元素是否相等
  • 如果栈顶元素和当前元素相等，出栈
  • 如果栈顶元素和当前的元素不等，将当前元素入栈
    从栈底部开始取出元素，构成字符串返回

class Solution {
    public String removeDuplicates(String S) {
        Deque<Character> stack=new LinkedList<>();
        int n=S.length();
        for(int i=0;i<n;i++){
            if(stack.isEmpty()){
                stack.push(S.charAt(i));
            }else{
                if(S.charAt(i)==stack.peek()){
                    stack.pop();
                }else{
                    stack.push(S.charAt(i));
                }
            }
        }
        StringBuilder bd=new StringBuilder();
        while(!stack.isEmpty()){
        	// 需要注意的是，双端队列的pollLast才是从栈的底端取第一个元素
        	// 对应的pollFirst与pop（）方法的作用是相同的
            bd.append(stack.pollLast());
        }
        return bd.toString();

    }
}

直接使用StringBuilder提供的栈

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.com/problems/remove-all-adjacent-duplicates-in-string/solution/shan-chu-zi-fu-chuan-zhong-de-suo-you-xi-4ohr/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

赏

谢谢你请我吃糖果

微信