# Replace spaces in string

import re

def replace_token_regex(s, token=" "):
return re.sub(token, '20%', s.strip())

def replace_token_inplace(s, token=" "):

for index, char in enumerate(s):
if ord(char) == ord(token):
s[index] = '20%'
return s

print replace_spaces_regex("Foo Bar ")
s = list("Foo Bar ")
replace_spaces_inplace(s)
print ''.join(s)


The run time complexity of the above code is $O(n)$, can it be further optimized? or is there any better way to do the above computation?

• Every character must be inspected, hence the complexity is $O(n)$.
– vnp
Dec 9 '14 at 5:37
• Do you mean '%20'? Do you actually want to perform URL percent-encoding, by any chance? Dec 9 '14 at 6:39
• Its just an example. There can be anything :) Dec 9 '14 at 6:40

If you want to avoid replace, a faster method would just split and join. This is faster simply because .split and .join are fast:

"20%".join(string.split(" "))


For a more thorough review, I'll point out that your functions aren't equivalent. The first strips whitespace and the second doesn't. One of them must be wrong!

In the second case:

def replace_token_inplace(s, token=" "):
for index, char in enumerate(s):
if ord(char) == ord(token):
s[index] = '20%'
return s


you are doing several non-idiomatic things. For one, you are mutating and returning a list. It's better to just not return it if you mutate:

def replace_token_inplace(s, token=" "):
for index, char in enumerate(s):
if ord(char) == ord(token):
s[index] = '20%'


Secondly, it'll probably be faster to do a copying transform:

def replace_token_inplace(s, token=" "):
for char in s:
if ord(char) == ord(token):
yield '20%'
else:
yield char


which can also be written

def replace_token_inplace(s, token=" "):
for char in s:
yield '20%' if ord(char) == ord(token) else char


or even

def replace_token_inplace(s, token=" "):
return ('20%' if ord(char) == ord(token) else char for char in s)


If you want to return a list, use square brackets instead of round ones.

Why not use the Python standard function:

"Foo Bar ".replace("20%"," ")


It's built-in, so experts have optimised this as much as possible.

• That solution seems to do the inverse of code in the question. Dec 9 '14 at 10:17
• "Foo Bar ".replace(" ", "20%") should produce the correct results. Here is a link to the documentation. Dec 9 '14 at 16:27
• I know that but I wanted to solve it without some library function just for learning purpose. Dec 9 '14 at 17:59