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?
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.