Python String Remove brackets Time Complexity-CodePudding

Suppose I wanna remove brackets from a string.

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

if I iterate through the string from end and slice out the specific index each time, it will take O(n) time for each slicing (I suppose, couldn't find the time complexity of string slicing). which pushes the total time complexity to O(n^2). And Space is O(1) I guess.

But if I convert my string to List using stringList=list(givenString) and instead of poping the element at specific index, I make that char at that index blank i.e. stringList[n]="" it only takes O(1) time. And latter I can iter through the list to join or use "".join(stringList). This keeps my time to O(n) but space is also O(n).

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

Is there any better way?

EDIT I asked this question in reference of this question on leetcode 1249 so I can't just remove all the Brackets from the string. That's why I didn't use replace.

I solved it like this

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

I was wondering if I could change the string s in place without driving the time or space complexity up.

CodePudding user response：

Your analysis of the two proposed solutions looks correct on the surface, but it's not using the built-in capabilities of Python in the most efficient way. I'd just do:

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

Each of the replace calls will be O(n).

CodePudding user response：

Turns out for long strings like "abc(d))qd()" * 10**5, str.translate is even faster than the str.replaces after all:

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

Code (Try it online!):

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()