1209. Remove All Adjacent Duplicates in String II

Loading...LeetCode

12/29/2020 Update:

传说中的一维消糖果，其实用stack最简单快捷，之前想复杂了...

本想简单把 Q1047 的解改一改变成双指针，但是TLE了。

1047. Remove All Adjacent Duplicates In String

每次执行删除操作之前，当前位置累计的重复字符数量memo[i]只取决于前一位置的重复字符数量memo[i-1]和当前字符是否于前字符相同s[i]==s[i-1]，所以可以近似看作一个bottom-up DP，只不过i不是一直向右移动，而是会在每次删除操作之后左移。

Stack

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        # we need to track the newly added ch and manipulate it -> stack
        stack = []
        # not only ch, but also it's continously duplicate amount
        # stack [(ch, n)]
        # once the n reaches k, we pop the tailed chs
        for ch in s:
            if stack and ch == stack[-1][0]:
                if stack[-1][1] + 1 == k:
                    stack.pop()
                else:
                    stack[-1][1] += 1
            else:
                stack.append([ch, 1])
        
        return "".join([x[1]*x[0] for x in stack])

Two Pointers (TLE)

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        i, j = 0, 1
        while s and i < len(s)-k+1:
            if j - i == k:
                s = s[:i]+s[j:]
                i = i-k if i>=k else 0
                j = i + 1
            elif s[j] == s[i]:
                j += 1
            else:
                i += 1
                j = i + 1
        return s

Pseudo DP

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        n = len(s)
        memo = [0 for _ in range(n)]
        memo[0] = 1
        i = 1
        while 0 <= i < len(s):
            if s[i] == s[i-1]:
                memo[i] = memo[i-1] + 1
                if memo[i] == k:
                    s = s[:i-k+1]+s[i+1:]
                    i = i - k
                    #print(s, i)
            else:
                memo[i] = 1
            i += 1
        return s