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

WechatIMG577.jpeg

题目描述

leetcode 第1047题:删除字符串中的所有相邻重复项
给出由小写字母组成的字符串 S,重复项删除操作会选择两个相邻且相同的字母,并删除它们。
在 S 上反复执行重复项删除操作,直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例:
输入:”abbaca”
输出:”ca”
解释:
例如,在 “abbaca” 中,我们可以删除 “bb” 由于两字母相邻且相同,这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 “aaca”,其中又只有 “aa” 可以执行重复项删除操作,所以最后的字符串为 “ca”。

解题方法


原址题解

  • 解题思路

这个题目可以理解为“俄罗斯方块”或者“消消乐”
把字符串逐个压栈,相同的字符抵消,最后剩余的就是答案

  • 复杂度

时间复杂度:O(n),n是字符串S的长度
空间复杂度:O(1)

  • 代码实现

python3

1
2
3
4
5
6
7
8
9
10
class Solution:
def removeDuplicates(self, S: str) -> str:
stack = []
n = len(S)
for i in range(n):
if stack and stack[-1] == S[i]:
stack.pop()
else:
stack.append(S[i])
return "".join(stack)

php

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
function removeDuplicates($S) {
$stack = [];
$n = strlen($S);
for($i=0;$i<$n;$i++){
if($stack && end($stack)==$S[$i]){
array_pop($stack);
}else{
array_push($stack,$S[$i]);
}
}
return implode("",$stack);
}
}
  • 文字草稿

S = “abbaca”
第1个字符入栈,[‘a’]
第2个字符入栈,[‘a’,’b’]
第3个字符入栈,[‘a’,’b’,’b’],字符b被抵消,剩余[‘a’]
第4个字符入栈,[‘a’,’a’],字符a被抵消,剩余[]
第5个字符入栈,[‘c’]
第6个字符入栈,[‘c’,’a’]
即最后的字符串为ca

-------------本文结束感谢您的阅读-------------
0%