Reverse String Function in Python (Primitive Steps)

Question

I tried coming up with a way to do a reverse string function without using the [ : : -1] method. I'm new to coding and am trying to only use the "primitive" steps. Below is my function and specifications. I was wondering if this is an efficient way to write the function. I appreciate any help. Thanks!

def reverse(word):
    x = -2                     #word in reversed order counter
    y = 1                      #starts counter to end "while" statement below
    reversed = word[-1]        #starts the reversed-word at last letter of word
    while len(word) > y:       #ending parameter for when all letters run through loop
        reversed += word[x]    #adds letters to reversed word starting at word[-2]
        x -= 1                 #moves position in word 1 to the left
        y += 1                 #increases the counter by 1
return reversed

No, it’s seriously inefficient, but there’s no reason to write your own in the real word regardless, so… — Ry-
– Ry- ♦, Commented Oct 11, 2013 at 19:54
Appending to a string n times will typically take O(n²) time, unless the string implementation performs the appropriate overallocation (Python's string type doesn't). So no, this isn't anywhere near efficient. — Fred Foo
– Fred Foo, Commented Oct 11, 2013 at 19:55
a better place to ask this would be codereview.stackoverflow.com — Joran Beasley
– Joran Beasley, Commented Oct 11, 2013 at 19:58
What do you mean by primitive steps? As you say, there's 101 variations of doing this on SO. Your code would only end up going towards one of those... I'm not sure what kind of answer you expect to this question... — Jon Clements
– Jon Clements, Commented Oct 11, 2013 at 19:59
I started the MIT computer science courses offered on youtube and the professor describes "primitive" as only those pieces of code that are necessary to have a Turing complete language. So I suppose variables, operators and conditionals. But thank you for pointing me to the codereview forum of stackoverflow. The question should have been posted there. Much appreciated! — craig
– craig, Commented Oct 11, 2013 at 20:25

rlms · Accepted Answer · 2013-10-11 20:14:46Z

1

Adding to a string is slow. It's probably best to make a list of the characters in the string in reversed order, then use the string method join on it.

Example code (fairly close to your original function):

def reverse(word):
    index = len(word)-1                  
    result = []      
    while index >= 0: 
        result.append(word[index]) 
        index -= 1 
    return "".join(result)

Better example code:

def reverse(word):
    word_list = []
    for i in range(len(word)-1, -1, -1):
        word_list.append(word[i])
    return "".join(word_list)

def reverse(word):
    return "".join(word[i] for i in range(len(word)-1, -1, -1))

Even better code:

def reverse(word):
    return "".join(reversed("abc"))

or

def reverse(word):
    return word[::-1]

But of course, the most efficient code is that with the fewest characters. [/sarcasm]

reverse =lambda s:s and s[-1]+reverse(s[:-1])or s

Yet another solution (I think it is likely to be slow):

def reverse(word):
    word_list = []
    for i in word:
        word_list.insert(0, word[i])
    return "".join(word_list)

edited Oct 11, 2013 at 20:14

answered Oct 11, 2013 at 20:04

rlms

11.1k8 gold badges47 silver badges62 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

Ry- Over a year ago

@jeremynealbrown: Read the first sentence of the question.

roman Over a year ago

why not for c in word: word_list.append(c) ...?

craig Over a year ago

Thanks. I was messing around with the idea of using append but then I realized that it doesn't work for a string. Didn't even know about the join method.

kindall Over a year ago

"Adding to a string is slow." This was optimized some time ago and is probably not as slow as you think. If the string has only one reference, as it would in this case, it's modified in place rather than being copied upon each concatenation.

kindall Over a year ago

Hard to say the speed differences without using timeit but yeah, having more than one variable pointing to a string disables this optimization.

|

ely · Accepted Answer · 2013-10-11 20:14:38Z

1

I like the functional-ish recursive way, but this may not be the best for Python:

def rev(w): 
    return rev(w[1:]) + w[0] if w else w

You'd want to include type checking or something, or possibly extend this a bit to handle any iterable and not just a string.

answered Oct 11, 2013 at 20:14

ely

77.8k36 gold badges158 silver badges234 bronze badges

1 Comment

Ry- Over a year ago

No, this is good. If you extended it a bit to handle every iterable, you’d have reversed :)

Collectives™ on Stack Overflow

Reverse String Function in Python (Primitive Steps)

2 Answers 2

8 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

8 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related