【一天一道Leetcode】删除字符串相邻重复项

01

题目描述

题目描述：

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

在S上反复执行重复项删除操作，

直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。

答案保证唯一。

示例：

输入："abbaca"
输出："ca"

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

提示：

1. 1 <= S.length <= 20000

2. S仅由小写英文字母组成。

02

方法和思路

由题目可知，

本题需要注意的要点有两个

1.两个相邻且相同字符会被删除。

(注意:是需要删除两个相同的字符)

2.删除字符串中两个相邻并且相同的字符可能会产生新的相邻并且相同的字符。

比如题目中的"abbaca"。删除bb后，会产生新的字符串aaca,
此时也需要将aa删除
最后的字符串为ca

我们根据要点可知，并不能一次字符串删除操作就达到最终目的，我们需要每次删除完一对相邻相同的字符后，再看新的字符串是否存在相邻相同的一对字符。

根据分析我们可以用一个数据结构，也就是栈，存储每次比较的结果。

同时可以从左到右的遍历一次字符串S的所有字符Si，和栈中的栈顶元素比较。

如果Si与栈顶元素相同，

则说明两个字符相邻且相同，或者是由于中间元素被删除后导致的间接相邻相同。

如果Si与栈顶元素不相同，

则说明两个字符无法被消除，满足题目条件，则把此时的字符Si入栈。

我们用字符串abbaca，和一个初始为空的栈描述一下代码处理过程。

初始情况，栈内为空，

字符串S指向第一个字符S0=a

由于栈为空，将S0=a入栈

字符串指针指向S1=b

此时对S1=b与栈顶元素a作出判断，

二者不相同，S1=b入栈

字符串指针指向S2=b

此时对S2=b,与栈顶元素b作出判断，

二者相同，S2=b与栈顶元素b消除

字符串指针指向S3=a

此时对S3=a与栈顶元素a作出判断，二者相同，S3=a与栈顶元素a消除

字符串指针指向S4=c

由于栈为空，将S4=c入栈

字符串指针指向S5=a

此时对S5=a与栈顶元素c作出判断，

二者不相同，S5=a入栈

字符串判断完毕

输出

栈中元素

我们用代码表示如下：

class Solution:
    def removeDuplicates(self, S: str) -> str:
        stk = list()
        for ch in S:
            if stk and stk[-1] == ch:
                stk.pop()
            else:
                stk.append(ch)
        return "".join(stk)