当前位置：首页 > article >正文

【百日算法计划】：每日一题，见证成长（020）

article 2024/9/27 12:15:17

题目

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

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
输入：“abbaca”
输出：“ca”

思路

栈的解法，判断字符与栈顶元素是否相等，相等则弹出栈顶元素，否则将字符押入栈（注意：不需要构造对象计数）

public class Code09 {
    //栈解法
    public String removeDuplicates(String s) {
        if (s == null) return null;
        Stack<Character> stack = new Stack<>();
        int n = s.length();
        for (int i = 0; i < n; i++) { //顺序处理每个字符
            char c = s.charAt(i);
            if (!stack.isEmpty() && c == stack.peek()){
                stack.pop();
            } else {
                stack.push(c);
            }
        }
        int size = stack.size();
        char[] chars = new char[size];
        for (int i = size-1; i >= 0; i--) {
            chars[i] = stack.pop();
        }
        String s1 = String.valueOf(chars);
        return s1;
    }   
}