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

苦逼的码农

共 2774字,需浏览 6分钟

 ·

2021-10-01 23:41

往期回顾

三分钟基础:什么是时间|空间复杂度

三分钟基础:什么是数组

三分钟基础:什么是链表

三分钟基础之链表训练:环形链表

三分钟基础之链表训练:环形链表升级版

三分钟基础之链表训练:链表相交

三分钟基础:什么是栈|队列

三分钟基础之栈训练:有效括号匹配


今天来做字符串消消乐,当然不是那个消消乐,是它的弟中弟中弟版,只需要相邻是重复的消掉就好了。


话不多说,直接肝题!




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


题意


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


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


示例


输入:abbaca

输出:ca


提示


答案保证唯一


1 <= S.length <= 20000

S 仅由小写英文字母组成


题目解析


水题,难度简单。


匹配到相邻的两个元素是相同的就消除你看有没有眼熟,像不像是括号匹配那道题。


呃,如果你不知道括号匹配那道题,看下面链接咧,我写过


栈,你告诉我这个括号配不配!


这种类型的题都算是匹配问题,只要是匹配问题,大家记住,在没有思路的时候,都可以考虑用栈碰一碰


既然看透了这道题的本质,那做法也就呼之欲出了。


维护一个栈,从左到右依次扫描字符串,让当前字符和栈顶元素比较:


  • 如果相同,证明当前两个元素相邻且相同或者由于之前删除了相同元素导致间接相邻且相同,此时栈顶元素出栈,当前字符不入栈。

  • 如果不同,则当前元素入栈。


如此反复,直至扫描结束,栈里剩下啥字符就是啥字符。


需要注意的是,删除两个相邻且相同的字符可能会产生新的相邻且相同的字符


图解


假设字符串 S = abbaca


首先初始化栈


# 初始化栈stack = []

根据“题目解析”中说的,如果当前元素与栈顶元素不同,则当前元素入栈。


所以第 1 步,当前元素为 a,栈为空,所以元素 a 入栈。



第 2 步,当前元素为 b,此时栈顶元素为 a,两者不相等,所以元素 b 入栈。


接下来第 3 步,当前元素为 b,栈顶元素为 b,两者相等,栈顶元素出栈。



for char in s:     if stack and stack[-1] == char:        stack.pop()


之后第 4 步,当前元素为 a,栈顶元素为 a,这就是由于删除两个相邻且相同的字符,产生了新的相邻且相同的字符。



最后两步没有相同的,直接入栈,输出栈内元素即可。


在这提醒一下编程语言直接用“栈”这个结构的,输出的时候要反转下字符串



因为从头到尾只遍历字符串 S 一次,所以时间复杂度为 O(n)


在这个过程中,维护了一个额外的栈,所以本解法空间复杂度为 O(n)


代码实现


Python 代码实现


class Solution:    def removeDuplicates(self, s: str) -> str:        # 初始化栈        stack = []
for char in s: # 如果"栈不为空"且"栈顶元素和当前元素相同"则栈顶元素出栈 if stack and stack[-1] == char: stack.pop() # 否则当前元素进栈 else: stack.append(char) # 栈内元素拼接成一个字符串 return ''.join(stack)


Java 代码实现


此处直接拿字符串当栈,省去了栈要转为字符串的操作。


class Solution {    public String removeDuplicates(String s) {        // 将 res 当做栈        StringBuffer res = new StringBuffer();        // top为 res 的长度        int top = -1;        for (int i = 0; i < s.length(); i++) {            char c = s.charAt(i);            // 当 top > 0,即栈中有字符时,当前字符如果和栈中字符相等,弹出栈顶字符,同时 top--            if (top >= 0 && res.charAt(top) == c) {                res.deleteCharAt(top);                top--;            // 否则,将该字符 入栈,同时top++            } else {                res.append(c);                top++;            }        }        return res.toString();    }}


好啦,图解这道题目长长的题到这里就结束啦。


这道题就很能说明问题,其实就是换汤不换药,穿上个马甲也不能装乌龟。


大家在做题的时候还是得仔细琢磨,不能过去了就是过去了


有问题,扔到留言区。


END

最后,欢迎大家加入帅地的知识星球,星球里有很多热爱学习的小伙伴,一群人一起学习不孤单。

并且你有任何学习上的疑问,帅地都会指导你应该如何学习,根据你的情况为你量身定制,在星球会提供如下服务:

1、【一对一咨询服务】48 小时以内详细回答你的任何问题,包括写作等等,这是知识星球最重要的功能。最近一周就回答了十几个 offer 选择,校招等学习路线问题。

2、【学习攻略】校招这方面比较有经验,帅地会提供完整的学习攻略,小白跟着帅地说的学习就行,这块会在最近出。

3、简历修改,项目等学习资源,offer 收割机嘉宾分享等等。

目前星球是专注于校招,在校生学习指导这块,一定可以让你少走弯路,已经有 490+ 位小伙伴加入,这里还有一些 20 元的优惠卷,如果你信的过帅地,那么欢迎你的加入。


想具体了解可以看这篇文章:我的四年大学


浏览 52
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报