题目
给定仅由小写字母组成的非空字符串,存在一个重复项删除操作,其会选择两个相邻且相同的字母,并删除它们。
请在字符串上反复执行重复项删除操作,直到无法继续删除,并在完成所有重复项删除操作后返回最终的新字符串。
例如:
给定一个字符串:aaabbaaaca,返回结果:ca
给定一个字符串:a,返回结果:a
实现思路1
- 使用
双指针
来实现 - 设置两个指针:slow、fast,初始值均为 0 ,同时用列表res存放字符串中所有字符
- 当 fast 小于字符串的长度时,执行循环,每次循环都把res中 fast 对应的字符放到 slow 指针下,并让 fast + 1
- 每次循环中,判断 slow 对应字符是否等于前一个字符。如果等于那么让 slow - 1,以便下次循环时重新设置res中 slow 前一个位置对应的字符,否则就让 slow + 1
- 当 fast 等于字符串的长度时,退出循环,此时 res 中从索引 0 到 slow 对应的所有字符,就是最终相邻不重复的字符,将其拼接为一个新字符串返回即可
代码实现1
def removeDuplicates(s):
res = list(s)
slow, fast = 0, 0
while fast < len(s):
res[slow] = res[fast]
if slow > 0 and res[slow] == res[slow - 1]:
slow -= 1
else:
slow += 1
fast += 1
return "".join(res[0:slow])
实现思路2
- 使用
栈
来实现 - 设置一个栈,用一个列表res来模拟
- 遍历字符串,如果res为空,则直接把当前字符添加到res;如果res非空且最后一个字符,恰等于当前字符,也就说明出现重复项需删除,于是对 res 执行出栈操作
- 遍历结束后,res中存放的就是最终相邻不重复的字符,将其拼接为一个新字符串返回即可
代码实现2
def removeDuplicates(s):
res = []
for i in s:
if res and res[-1] == i:
res.pop()
else:
res.append(i)
return "".join(res)