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

妖狐艹你老母 2023-10-13 22:31 8阅读 0赞

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

*  题干背景
 *  重要思路
 *  理解思路后代码实现

# 题干背景 #

[力扣入口-1047. 删除字符串中的所有相邻重复项][-1047.]

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

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

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

示例：

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

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

# 重要思路 #

1.  使用ArrayDeque，效果比Deque更佳。
2.  注意最后是`res = stack.pop() + res`，不是`res += stack.pop()`，因为栈中元素弹出后顺序需要调整。

# 理解思路后代码实现 #

// 1047. 删除字符串中的所有相邻重复项
    public String removeDuplicates(String S){
        
        String res = "";
        ArrayDeque<Character> stack = new ArrayDeque<>();
        char temp;
        for(int i = 0; i < S.length(); i++){
        
            temp = S.charAt(i);
            if(stack.isEmpty() || stack.peek() != S.charAt(i)){
        
                stack.push(temp);
            }else{
        
                stack.pop();
            }
        }
        while(!stack.isEmpty()){
        
            res = stack.pop() + res;
        }
        return res;
    }

**参考资料**：[1047. 删除字符串中的所有相邻重复项][1047.]

[-1047.]: https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/description/
[1047.]: https://programmercarl.com/1047.%E5%88%A0%E9%99%A4%E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B8%AD%E7%9A%84%E6%89%80%E6%9C%89%E7%9B%B8%E9%82%BB%E9%87%8D%E5%A4%8D%E9%A1%B9.html#%E6%AD%A3%E9%A2%98