在每次迭代中我都是 'redefining/reallocating' 或恢复一个变量，这需要额外的 space 吗？

Question

我已经为以下问题编写了解决方案：https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-ii/

为了总结这个问题，我们得到了一个integer k，我们需要remove duplicates of length k，来自input string s。

在我的解决方案中，我写出了所有可能的重复项，这是一个包含 26 个元素的数组。然后我遍历输入字符串 s，并从中删除重复项，或者更确切地说，我使用切片 redefine s:

def removeDuplicates(s: str, k: int) -> str:
        dup = [k * i for i in "qwertyuiopasdfghjklzxcvbnm"]

        pointer1 = 0
        while pointer1+k<len(s):
            if s[pointer1:pointer1+k] in dup:
                s = s[:pointer1] + s[pointer1+k:]
                if pointer1>1:
                    pointer1-=2*k

            if s[-k:len(s)] in dup:
                s = s[:-k]

            else:
                pointer1+=1

        return s

我的理解是 time complexity is O(n)，其中 n 是输入字符串的长度，因为在最坏的情况下我们遍历整个字符串而不删除任何字符。这是正确的吗？

space complexity是我比较不确定的地方，因为每次我发现一个重复项，我都在重新定义s，所以需要为此分配'new' space。说 space 复杂度也是 O(n) 对吗？

Answer 1

实际上，这取决于您使用的语言。就像 java 有垃圾收集器一样，python 也有类似的东西。但是在 c 中我们可以说我们有 O(n) space 复杂性。

在每次迭代中我都是 'redefining/reallocating' 或恢复一个变量，这需要额外的 space 吗？

At each iteration I am 'redefining/reallocating' or restoring a variable, does this take extra space?

python

time-complexity

space-complexity