Leetcode weekly contest 156 删除字符串中的所有相邻重复项 II Remove All Adjacent Duplicates in String II

目录

给你一个字符串 s，「k 倍重复项删除操作」将会从 s 中选择 k 个相邻且相等的字母，并删除它们，使被删去的字符串的左侧和右侧连在一起。

你需要对 s 重复进行无限次这样的删除操作，直到无法继续为止。

在执行完所有删除操作后，返回最终得到的字符串。

本题答案保证唯一。

示例 1：

输入：s = "abcd", k = 2
输出："abcd"
解释：没有要删除的内容。

示例 2：

输入：s = "deeedbbcccbdaa", k = 3
输出："aa"
解释： 
先删除 "eee" 和 "ccc"，得到 "ddbbbdaa"
再删除 "bbb"，得到 "dddaa"
最后删除 "ddd"，得到 "aa"

示例 3：

输入：s = "pbbcggttciiippooaais", k = 2
输出："ps"

提示：

• 1 <= s.length <= 10^5
• 2 <= k <= 10^4
• s 中只含有小写英文字母。

AC 代码：

递归结构，每次执行函数，就删除所有 k 个相邻的字母，得到新字符串，如果新字符串和老字符串是相同的，就返回这个字符串，否则再对新字符串执行该操作。

每次操作具体过程如下：

1. 先顺序统计出字符串中相邻相同字符出现次数例如上面示例 3

   p 0 0
   b 1 2
   c 3 3
   g 4 5
   t 6 7
   …..

   代表 p 是从第 0 个到第 0 个位置，一共一个
   b 从第 1 个到第 2 个位置，一共连续两个

2. 对于每一组看是否要删除，从而计算要放到新串里几个。（就是变量 r）

   举例说，如果 k 是 2，而有一个字符连续出现 5 次，要放到新串的个数是 5 % 2，就是 5 除以 2 的余数，就是 1 个。

3. 复制到新串

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        d = []
        i = 1
        l = 0
        while i < len(s):
            if s[l] != s[i]:
                d.append([l, i - 1])
                l = i;
            i += 1
        d.append([l, i - 1])
        ns = ''
        for x in d:
            c = x[1] - x[0] + 1
            if c >= k:
                r = c % k
                if r > 0:
                    ns += s[x[0]: x[0]+r]
            else:
                ns += s[x[0]: x[1]+1]
        if len(ns) == len(s):
            return ns
        return self.removeDuplicates(ns, k)