Replace spaces in string

Question

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?

• vnp: Every character must be inspected, hence the complexity is \$O(n)\$.
• 200_success: Do you mean '%20'? Do you actually want to perform URL percent-encoding, by any chance?
• CodeYogi: Its just an example. There can be anything :)

Answer 1

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.

Answer 2

Why not use the Python standard function:

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

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

• 200_success: That solution seems to do the inverse of code in the question.
• iLoveTux: "Foo Bar ".replace(" ", "20%") should produce the correct results. Here is a link to the documentation.
• CodeYogi: I know that but I wanted to solve it without some library function just for learning purpose.