Using memory while deleting extra spaces

Question

I need to remove extra spaces in string. And I need to use O(1) memory. Is it possible to not use lists, because lists use more memory than strings (I've checked it with sys.getsizeof()) or when I use split() I'm still using O(1) memory?

There is code

s = input()
s = s.split('_')
s = list(filter(lambda a: a != '', s))
print('_'.join(s))

Strings are immutable in python, so removing spaces will result in a new string of comparable length to the original. That makes it impossible to solve this problem in O(1) space. — Paul Hankin, Mar 01 '21 at 09:52

score 1 · Answer 1 · answered Mar 01 '21 at 08:32

1

I would usually do this to remove extra spaces

text = ' '.join(text.split()).strip()

Though if you don't want to use list you can use regex

import re
text = re.sub(r' {2,}', ' ', text).strip()

answered Mar 01 '21 at 08:32

Ron Serruya

3,988
1
16
26

1

Is there a way to check that this is `O(1)` ? – Ivan Mar 01 '21 at 08:35
It seems the second method satisfies the condition and use O(1) memory – PrintScreenSys Mar 01 '21 at 08:50
How do you know for sure? – Ezequiel Muns Mar 01 '21 at 08:55
It's not O(1) in time or space. It's O(n) time, O(n) space (and no solution can be better in terms of efficiency). – Paul Hankin Mar 01 '21 at 09:53

Using memory while deleting extra spaces

1 Answers1