同系列文章导读:【数据结构与算法】导读

所有文章均在本博客首发,其他平台同步更新

如果有更好的方法,欢迎指点,共同进步~~

有其他语言代码也可在留言区留言,谢谢

发表评论时请填写正确邮箱,以便于接收通知【推荐QQ邮箱】


  • 时间:2022-05-25
  • 题目序号:1047
  • 难度:简单

问题描述

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

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

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

来源:力扣(LeetCode)

示例

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

提示

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

解题思路

题解部分参考自代码随想录。如有侵权,请联系进行删除~~
  • 由题目内容我们可以知道:字符串是由纯字母组成,要删除的元素是相邻的
  • 删除某元素后,后续元素继续前移,如果和被删除元素前的元素再次形成相邻重复,就继续删除,直到删除不了为止
  • 本题我们可以用栈来解决

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

  • 配合上面的动图,首先结合题目要求,了解要删除元素的特点
  • 首先遍历字符串,当栈不为空或者栈顶元素和当前字符不等时,将其入栈
  • 如果遍历的字符和栈顶元素相等,则将栈顶元素弹出(实现删除操作)
  • 循环结束后,将栈内元素弹出并拼接,就是删除重复元素后的字符串

代码实现

class Solution {
    public String removeDuplicates(String s) {
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < s.length(); i++){        // 遍历字符串
            char ch = s.charAt(i);
            if(stack.isEmpty() || stack.peek() != ch){      // 符合条件入栈
                stack.push(ch);
            }else{      // 栈内元素和当前字符重复,弹出
                stack.pop();
            }
        }
        // 目前栈内元素即为去重后的元素,依次弹出并拼接
        String result = "";
        while(!stack.isEmpty()){
            result = stack.pop() + result;      // 注意顺序,pop在前,拼接在后
        }
        return result;
    }
}

总结

  • 本题整体比较容易理解,需要注意的就是最后字符串拼接时,需要注意顺序,先pop,在拼接,否则最终顺序就是结果的逆序
  • 在字符串拼接时,还可以进行优化,使用StringBuilder,因为在字符串使用+进行拼接时,底层就是使用StringBuilderappend方法,在拼接完后,使用reverse反转顺序即可

END

本文作者: 文章标题:【每日一题】删除字符串中的所有相邻重复项
本文地址:https://www.hellocode.top/archives/118/
版权说明:若无注明,本文皆HelloCode原创,转载请保留文章出处。
最后修改:2022 年 05 月 25 日
如果觉得我的文章对你有用,请随意赞赏