0
\$\begingroup\$
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?

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

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.

\$\endgroup\$
0
\$\begingroup\$

Why not use the Python standard function:

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

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.