题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给一个字符串和一个整数 k，要求把其中所有相邻的连续的，长度超过k的项删除，返回最后的字符串。

思路分享

  • 除了暴力的检测到相邻字符，删除后从头到尾再检测一边这种。其实可以通过记录每个字符的重复计数来加速过程。

  • 比如本题用栈记录遍历过的字符，以及对应的重复计数（一个字符与上一个字符相同时则加一），在这个计数大于 k 时，把这个字符弹栈 k 次。

代码解答（强烈建议自行解答后再看）

  • 参考题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        stk = list()
        rec = list()
        for i, c in enumerate(s):
            if stk and c == stk[-1]:
                rec.append(rec[-1]+1)
            else:
                rec.append(1)
            stk.append(c)

            if rec[-1] == k:
                while rec[-1] != 1:
                    stk.pop()
                    rec.pop()
                stk.pop()
                rec.pop()

        return "".join(stk)