Constraints

Can I assume the string is ASCII?
- Yes
- Note: Unicode strings could require special handling depending on your language

Algorithm

Since Python strings are immutable, we'll use a list of words instead to exercise in-place string manipulation as you would get with a C string.

create a list as a string builder for reversed sentence

split string into words
for each word
- create a list as a string builder for reversed word
- for each character in current word:
- - insert character into the begining of reversed word string
- - inserts reversed word string into the reversed sentence list

Complexity:

Time: O(len(string))
Space: O(len(string))



In [28]:

    
def reverse_words(string):
    if not string:
        return string
    newString = []
    for word in string.split():
        newWord = []
        for char in word:
            newWord.insert(0, char)
        newString.insert(0, "".join(newWord))
    return " ".join(newString)

Pythonic way

You can achive the same goal in a concise way by using python's list modidication methods as follows:



In [24]:

    
def reverse_words2(string):
    string = list(string)
    string.reverse()
    return "".join(string)

def reverse_words3(string):
    return string[::-1]

Unittests



In [23]:

    
from nose.tools import assert_equal


def testWith(func):
    assert_equal(reverse_words("this is an Example."), ".elpmaxE na si siht")
    assert_equal(reverse_words("hello friend"), "dneirf olleh")
    assert_equal(reverse_words("COOL"), "LOOC")
    assert_equal(reverse_words(None), None)
    print('Success: reverse_words')
    
testWith(reverse_words)
testWith(reverse_words2)
testWith(reverse_words3)









    



Success: reverse_words
Success: reverse_words
Success: reverse_words

Benchmark



In [27]:

    
import timeit
print "reverse_words", timeit.timeit(
    "reverse_words('this is an Example.')",
    "from __main__ import reverse_words", number=99000)
print "reverse_words2", timeit.timeit(
    "reverse_words2('this is an Example.')",
    "from __main__ import reverse_words2", number=99000)
print "reverse_words3", timeit.timeit(
    "reverse_words3('this is an Example.')",
    "from __main__ import reverse_words3", number=99000)









    



reverse_words 0.73145699501
reverse_words2 0.122512102127
reverse_words3 0.0340781211853



In [2]:

    
print "hellasdasd"









    



hellasdasd



In [ ]: