Pemula Exercism • python

Reverse String

Ringkasan Tantangan

Reverse a given string.

Introduction

Reversing strings (reading them from right to left, rather than from left to right) is a surprisingly common task in programming.

For example, in bioinformatics, reversing the sequence of DNA or RNA strings is often important for various analyses, such as finding complementary strands or identifying palindromic sequences that have biological significance.

Instructions

Your task is to reverse a given string.

Some examples:

Turn "stressed" into "desserts".
Turn "strops" into "sports".
Turn "racecar" into "racecar".

Dig Deeper

Sequence Slicing

Sequence Slice with Negative Step

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

This approach uses Python’s negative indexes and sequence slices to iterate over the string in reverse order, returning a reversed copy.

index from left ⟹

0 👇🏾	1 👇🏾	2 👇🏾	3 👇🏾	4 👇🏾	5 👇🏾
P	y	t	h	o	n
👆🏾 -6	👆🏾 -5	👆🏾 -4	👆🏾 -3	👆🏾 -2	👆🏾 -1

⟸ index from right

Slices use [<start> : <stop> : <step>] syntax. The space before the first : indicates which index to start iterating from (inclusive), the space before the second : indicates which index to stop before (exclusive), and the final space after the second : indicates the direction of iteration and size of the ‘step’. A positive step moves left —> right and a negative step moves right —> left. If start/stop indexes are omitted, Python assumes ‘start of string’ and ‘end of string’. Omitting the step defaults to a step of +1, but any size step can be used. Slices return a copy of the original object. This same syntax works on strings, bytearray, lists, tuples, and ranges, which are all sequence types.

Reverse slicing has O(n) time complexity - the amount of time/work scales directly with the length of the string being iterated through and reversed. And since slicing returns copy, the space for the copy also scales with the size of the input.

Using a slice on a string is roughly equivalent to looping over the string from the right-hand side, appending each codepoint to a new string. However, the code below takes O(n + n) best case and O(n**2) worst case due to the operations needed for string concatenation.

def reverse(text):
  output = ''
  for index in range(-1, -(len(text)+1), -1):
    output += text[index] 
  return output

Iteration and Concatenation

def reverse(text):
    output = ''
    for codepoint in text:
        output = codepoint + output
    return output

The variations here all iterate over the string, concatenating each codepoint to a new string. While this avoids all use of built-ins such as range(), reversed(), and list.reverse(), it incurs both a memory and speed penalty over using a reverse slice.

Strings are immutable in Python. Using concatenation via + or += forces the re-creation of the ‘output’ string for every codepoint added from the input string. That means the code has a minimum time complexity of O(m + n), where n is the length of the text being iterated over, and m is the number of concatenations to the ‘output’ string. For some more detail on O(n + m) vs O(n), see this Stack Overflow post. The code also uses O(n) space to store ‘output’.

As input strings grow longer, concatenation can become even more problematic, and performance can degrade to O(n**2), as longer and longer shifts and reallocations occur in memory. In fact, the “standard” way to describe the time complexity of this code is to say that is O(n**2), or quadratic.

Interestingly, CPython includes an optimization that attempts to avoid the worst of the shift and reallocation behavior by reusing memory when it detects that a string append is happening. Because the code above prepends the codepoint to the left-hand side of ‘output’, this optimization cannot be used. Even in cases where strings are appended to, this optimization cannot be relied upon to be stable and is not transferable to other implementations of Python.

For some interesting reading on this topic, see these Stack Overflow posts:

To see the difference between reverse slicing and looping in terms of steps, check out slicing verses iterating+concatenation at the PythonTutor site.

Variation #1: Using a While Loop and a Negative Index

def reverse(text):
    output = '' 
    index = -1
   
    while index >= -len(text):
        output += text[index]
        index -= 1
    return output

This solution uses a while loop to “count down” the length of the string using a negative index. Each number is used to index into the input string and concatenate the resulting codepoint to a new string. Because each index is further from zero than the last, this has the effect of “iterating backward” over the input string.

This approach incurs additional overhead for length checking the input string repeatedly in the loop, and setting/decrementing the index variable, both of which can be avoided by using the built-in range() object. Overall, this was the slowest of the three variations when timed.

Variation #2: Using a While Loop with a Positive Index

def reverse(text):
    result =''
    index = len(text)-1
    
    while index >= 0:
        result += text[index]
        index -= 1
    return result

This solution uses a while loop to “count down” the length of the string until it reaches zero using a positive index. Each number is used to index into the input string and concatenate the resulting codepoint to a new string. Because each index is closer to zero than the last, this has the effect of also “iterating backward” over the input string. Algorithmically, this takes as much tine and space as the code samples above, since it uses an intermediate string for the reversal and must loop through every codepoint in the input.

Timings vs Reverse Slice

As seen in the table below, all of these approaches are slower than using a reverse slice. Interestingly, iteration + prepending to the string is fastest in this group for strings under length 1420. But keep in mind that in general, string concatenation and prepending should be avoided for any ‘industrial strength’ use cases.

string length >>>>	5	11	22	52	66	86	142	1420	14200	142000
reverse slice	1.66e-07	1.73e-07	1.88e-07	1.12e-07	2.15e-07	2.32e-07	3.46e-07	1.42e-06	1.18e-05	1.15e-04
reverse string prepend	4.28e-07	8.05e-07	1.52e-06	3.45e-06	4.82e-06	5.55e-06	9.83e-06	2.23e-04	2.96e-03	5.17e-01
reverse positive index	4.65e-07	8.85e-07	1.73e-06	3.70e-06	4.83e-06	6.55e-06	1.01e-05	1.54e-04	1.60e-03	2.61e-02
reverse negative index	5.65e-07	1.32e-06	2.61e-06	5.91e-06	7.62e-06	4.00e-06	1.62e-05	2.16e-04	2.19e-03	2.48e-02

Measurements were taken on a 3.1 GHz Quad-Core Intel Core i7 Mac running MacOS Ventura. Tests used timeit.Timer.autorange(), repeated 3 times. Time is reported in seconds taken per string after calculating the ‘best of’ time. The timeit module docs have more details, and note.nkmk.me has a nice summary of methods.

Backward iteration with Range

Backward Iteration with Range

def reverse(text):
    output = ""
    for index in range(len(text) - 1, -1, -1): #For 'Robot', this is 4 (start) 0 (stop), iterating (4,3,2,1,0)
        output += text[index]
    return output

These variations all use the built-in range() object to iterate over the input text from right —> left, adding each codepoint to the output string. This is the same as iterating over the text backward using one or more index variables, but incurs slightly less overhead by substituting range() for them. Note that the code above also avoids prepending to the output string.

For very long strings, this code will still degrade to O(n**2) performance, due to the use of string concatenation. Using ''.join() here can avoid heavy concatenation penalty as strings grow longer and the CPython string append optimization mentioned in the iteration and concatenation approach breaks down.

Variation #1: Forward Iteration in Range, Negative Index

def reverse(text):
    output = ''

    for index in range(1, len(text) + 1):
        output += text[-index]
    return output

This version iterates left —> right using a positive range() and then prepends to the string by using a negative index for the codepoint. This has the same faults as variation #1, with the added cost of prepending via concatenation.

Variation #2: Feed Range and the Index into Join()

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

This version omits the intermediary output string, and uses "".join() directly in the return. Within the join() call, range() is used with a negative step to iterate over the input text backward.

This strategy avoids the penalties of string concatenation with an intermediary string. It is still O(n) in time complexity, and is slower than reverse indexing due to the calls to join(), len() and range(), and the creation of the generator expression.

Because of the aforementioned string append optimization in CPython, this approach will benchmark slower for strings under length 1000, but becomes more and more efficient as the length of the string grows. Since the CPython optimization is not stable nor transferable to other versions of Python, using join() by default is recommended in any situation where the string concatenation is not strictly repetition and length constrained.

Timings vs Reverse Slice

As a (very) rough comparison, below is a timing table for these functions vs the canonical reverse slice:

string length >>>>	5	11	22	52	66	86	142	1420	14200	142000
reverse slice	1.68e-07	1.74e-07	1.83e-07	2.07e-07	2.14e-07	2.29e-07	3.51e-07	1.50e-06	1.19e-05	1.17e-04
reverse negative range	5.89e-07	9.93e-07	1.78e-06	3.69e-06	4.71e-06	5.83e-06	9.61e-06	1.39e-04	1.46e-03	1.81e-02
reverse positive range	6.20e-07	1.14e-06	2.23e-06	4.54e-06	5.74e-06	7.38e-06	1.20e-05	1.70e-04	1.75e-03	2.07e-02
reverse range and join	8.90e-07	1.31e-06	2.14e-06	4.15e-06	5.22e-06	6.57e-06	1.06e-05	1.05e-04	1.04e-03	1.07e-02

Source: Exercism python/reverse-string

💡 Lihat Solusi

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