删除字符串中所有相邻重复项【简单】

题目

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

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

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

示例：

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

提示：

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

思路

1、我们使用一个栈来作为容器存储数据。
2、我们把字符串s每个charAt取出，然后判断栈如果为空，或者栈的元素不等于当前的ch，就可以入栈
3、然后我们就可以两两取出。
4、最后剩下的不满足条件的就是我们需要的内容。
5、我们再用一个字符串拼接就是答案

代码【java】

class Solution {
    public String removeDuplicates(String s) {
        Stack<Character> stack = new Stack<>();
        char ch;
        for(int i =0;i<s.length();i++){
            // 取出s中的每个元素开始判断
            ch = s.charAt(i);
            // 如果栈内没有元素或者取出的元素不是当前的ch，就可以入栈
            if(stack.isEmpty() || stack.peek()!=ch){
                stack.push(ch);
                // 否则我们就取出该元素（因为两两配对了）
            }else{
                stack.pop();
            }
        }

        // 经过上面的for循环这里的元素就是我们所需要的。我们直接字符串拼接，搞定
        String res ="";
        while(!stack.isEmpty()){
            res = stack.pop()+res;
        }
        return res;
    }
}