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

力扣传送门(opens new window)

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

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

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

示例：

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

解题思路：

根据题意的充分理解，我们可分析如下：

多组相邻重复项，我们无论先删除哪一项，都不会影响最终结果。
删除当前项是需要拿上一项出来对比的，所以我们需要用临时栈存放之前的内容。
当前项和栈顶一致，弹出栈顶抵消即可。若不一致，压入栈留存，供后续使用。

代码实现：

方法一：

import java.util.Stack;

class Solution {
    Stack<Character> stack = new Stack<>();
  
    public String removeDuplicates(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        // 将字符串转换为字符数组
        char[] ch = s.toCharArray(); 
  
        for (int i = 0; i < ch.length; i++) {
            // 如果栈为空，直接将当前字符入栈
            if (stack.isEmpty()) { 
                stack.push(ch[i]);
            } else {
                // 获取栈顶元素
                char top = stack.peek(); 
                // 如果当前字符与栈顶元素相同，则说明出现重复，将栈顶元素出栈
                if (top == ch[i]) { 
                    stack.pop();
                    // 跳过后续代码，继续处理下一个字符
                    continue; 
                } else { 
                    // 如果当前字符与栈顶元素不同，将当前字符入栈
                    stack.push(ch[i]);
                }
            }
        }

        // 构建最终的字符串
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            // 将栈中的字符依次插入到字符串的开头
            sb.insert(0, stack.pop()); 
        }
        // 返回最终的字符串结果
        return sb.toString(); 
    }
}

方法二：

class Solution {
    public String removeDuplicates(String s) {

        StringBuilder sb = new StringBuilder();
        int top = -1;
        for (int i = 0; i < s.length(); i++) {
            if (top >= 0 && sb.charAt(top) == s.charAt(i)) {
                // 如果当前字符与栈顶元素相同，从结果字符串中删除栈顶元素
                sb.deleteCharAt(top);  
                // 栈顶指针减一
                top--;  
            } else {
                // 如果当前字符与栈顶元素不同，将当前字符添加到结果字符串中
                sb.append(s.charAt(i));  
                // 栈顶指针加一
                top++;  
            }
        }
        // 返回最终的字符串结果
        return sb.toString();  
    }
}