current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 0 down vote favorite 
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?

share|improve this question
1  
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? – 200_success♦ Dec 9 '14 at 6:39
    
Its just an example. There can be anything :) – CodeYogi Dec 9 '14 at 6:40
up vote 3 down vote accepted

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.

share|improve this answer
up vote 0 down vote

Why not use the Python standard function:

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

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

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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