题目描述

[EN | CN]

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

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

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

示例:

1
2
输入:"abbaca"
输出:"ca"

解释:

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

提示:

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

解法 1:栈

用一个数组来表示一个栈,然后遍历原字符串,若遍历到的字符与栈顶元素(数组最后一个元素)相同,则弹出栈顶,否则将该字符插入栈顶。

假设字符串长度为 $n$,那么

  • 时间复杂度为 $O(n)$,遍历一遍;
  • 空间复杂度为 $O(n)$,存储结果。

实现与结果如下:

1
2
3
4
5
6
7
8
9
class Solution:
    def removeDuplicates(self, S: str) -> str:
        ret = []
        for char in S:
            if ret and char == ret[-1]:
                ret.pop()
            else:
                ret.append(char)
        return ''.join(ret)
  • 执行用时:64 ms,在所有 Python3 提交中击败了 92.49% 的用户。

  • 内存消耗:13.9 MB,在所有 Python3 提交中击败了 7.14% 的用户。

解法 2:正则

正则表达式算是有点「作弊」的手段了。。。但是题目也没规定不能用。这里也记录一下吧。

这里用的正则表达式为 ([a-zA-Z])\1,其中

  • 小括号圈住的内容表示分组,也就是说这里匹配的那个字母就是第一个分组;
  • \1 表示匹配第一个分组,跟前面合在一起的意思就是匹配连续两个相同的字母。

实现与结果如下:

1
2
3
4
5
6
7
import re
class Solution:
    def removeDuplicates(self, S: str) -> str:
        s, last_s = S, ''
        while s != last_s:
            s, last_s = re.sub(r'([a-zA-Z])\1', '', s), s
        return s
  • 执行用时:84 ms,在所有 Python3 提交中击败了 57.39% 的用户。
  • 内存消耗:13.7 MB,在所有 Python3 提交中击败了 7.14% 的用户。