Leetcode 1209. Remove All Adjacent Duplicates in String II

文章作者:Tyan
博客:noahsnail.com  |  CSDN  |  简书

1. Description

Remove All Adjacent Duplicates in String II

2. Solution

解析:Version 1,使用数据结构栈来解决这个问题,时间复杂度O(N)。字符每次入栈之前都与栈顶元素进行比较,如果不同,则入栈元组,元组元素为当前字符以及字符个数1,如果字符相同且栈顶相同字符个数不等于k-1,也入栈元组,元组元素为当前字符以及连续相同字符个数,值为栈顶字符的个数加1,否则,移除栈顶的k-1个字符。

  • Version 1
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def removeDuplicates(self, s: str, k: int) -> str:
res = []
for ch in s:
if not res or res[-1][0] != ch:
res.append((ch, 1))
else:
if res[-1][1] == k -1:
del res[-k+1:]
else:
res.append((ch, res[-1][1] + 1))
res = [x[0] for x in res]
return ''.join(res)

解析:另一种使用栈的方式,当前字符与栈顶字符相同时,只更新栈顶字符的个数。

  • Version 2
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def removeDuplicates(self, s: str, k: int) -> str:
res = []
for ch in s:
if not res or res[-1][0] != ch:
res.append([ch, 1])
else:
if res[-1][1] == k -1:
res.pop()
else:
res[-1][1] += 1
res = [x[0] * x[1] for x in res]
return ''.join(res)

Reference

  1. https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-ii/
如果有收获,可以请我喝杯咖啡!