Python字符串移除方括号时间复杂性

Question

假设我想从字符串中移除方括号。

string="abc(d))qd()"
for x in range(len(string)-1,-1,-1):
if string[x] in ["(",")"]:
string=string[:x]+string[x+1:]
return string

如果我从末尾迭代字符串，每次都切片出特定的索引，那么每次切片都需要O(n(时间(我想，找不到字符串切片的时间复杂性(。这将总时间复杂度推到O(n^2(。空间是O(1(。

但是，如果我使用stringList=list(givenString)将字符串转换为List，而不是在特定索引处弹出元素，我会将该索引处的char设为空，即stringList[n]=""，它只需要O(1(时间。然后我可以通过列表加入或使用"".join(stringList)。这使我的时间保持为O(n(，但空间也是O(n(。

lis=list(string)
for x in range(len(lis)):
if string[x] in ["(",")"]:
lis[x]=""
return "".join(lis)

有更好的方法吗？

EDIT我在leetcode 1249上参考这个问题提出了这个问题，所以我不能只从字符串中删除所有括号。这就是为什么我没有使用replace。

我像这个一样解决了它

class Solution:
def minRemoveToMakeValid(self, s: str) -> str:
openBra=[]
closeBra=[]
for x in range(len(s)):
if s[x] in ["(",")"]:
if s[x]==")":
if len(openBra)==0:
closeBra.append(x)
else:
openBra.pop()
else:
openBra.append(x)
bras=set(openBra+closeBra)
print(bras)
ret=""
for x in range(len(s)):
if x not in bras:
ret+=s[x]
return ret

我想知道我是否可以在不增加时间或空间复杂性的情况下更改字符串s。

Answer 1

对于像"abc(d))qd()" * 10**5这样的长字符串，str.translate毕竟比str.replace更快：

132.0 ms  listy
8.5 ms  replaces
2.0 ms  translate
2.1 ms  translate2
82.0 ms  re_sub

代码(在线试用！(：

from timeit import timeit
import re
string="abc(d))qd()"
def listy(string):
lis=list(string)
for x in range(len(lis)):
if string[x] in ["(",")"]:
lis[x]=""
return "".join(lis)
def replaces(string):
return string.replace('(', '').replace(')', '')
def translate(string):
return string.translate(str.maketrans('', '', '()'))
def translate2(string, table=str.maketrans('', '', '()')):
return string.translate(table)
def re_sub(string):
return re.sub('[()]', '', string)
funcs = listy, replaces, translate, translate2, re_sub
for f in funcs:
print(f(string))
string *= 10**5
for _ in range(3):
for f in funcs:
t = timeit(lambda: f(string), number=1)
print('%5.1f ms ' % (t * 1e3), f.__name__)
print()

Answer 2

您对两个拟议解决方案的分析表面上看起来是正确的，但它并没有以最有效的方式使用Python的内置功能。我就这么做：

return string.replace('(', '').replace(')', '')

每个replace调用将是O(n(。