Reversing words of a string without using inbuilt functions

Question

I was wondering if I could reverse a string without using collections and in-built functions of string, Please do add your thoughts on the approach and if possible do share your way of the solution.

# Reversing a string with a simple approach
# Ex: John Doe -> Doe John

str1= "Happy new year! 2022"
temp = ""
final_str = ""
space_counter = 0
print(f"string: {str1}\nlen: {len(str1)}")
for index in range(len(str1)):
    # print(index, ":", str1[index])
    char = str1[index]
    if char == " ":
        space_counter += 1
        if space_counter == 1:
            a_str = temp
        elif space_counter == 2:
            b_str = temp + " " + a_str
            a_str = b_str
            space_counter = 1
        final_str = a_str
        temp = ""
    elif index == len(str1) - 1:
        temp += char
        if final_str != "":
            final_str = temp + " " + final_str
        else:
            final_str= temp
    else:
        temp += char
print(f"Reversed_string: {final_str}\nlen: {len(final_str)}")

# Output:
# string: Happy new year! 2022
# len: 20
# Reversed_string: 2022 year! new Happy
# len: 20 

Answer 1

Write functions

You show the reversal of two strings: John Doe and Happy new year! 2022. But your code can only reverse one string. If you wanted to reverse the other string as well, you'd have to duplicate the code.

Instead, write a function. They can be called multiple times.

def reverse_words(sentence):
    ... your code here ...
    return final_str

str1 = "John Doe"
reversed1 = reverse_words(str1)
print(f"string: {str1}\nlen: {len(str1)}")
print(f"Reversed_string: {reversed1}\nlen: {len(reversed1)}")

str2 = "Happy new year! 2022"
reversed2 = reverse_words(str2)
print(f"string: {str2}\nlen: {len(str2)}")
print(f"Reversed_string: {reversed2}\nlen: {len(reversed2)}")

When writing functions, use type-hints and """doc-strings""" to provide additional information about how to use the function:

def reverse_words(sentence: str) -> str:
    """
    Reverse the words of a string.

    >>> reverse_words("John Doe")
    'Doe John'

    >>> reverse_words("Happy new year! 2022")
    '2022 year! new Happy'
    """

    ... your code here ...

    return final_str

With the above function definition, help(reverse_words) will describe the function in much the same way that help(print) describes the print function.

As a bonus, the >>> text in the """doc-string""" can be used for testing, via the doctest module.

Variable Naming

What is space_counter? At first read, I thought you were counting spaces, but it turns out that isn't quite correct:

space_counter = 0
for ...:
    if char == " ":
        space_counter += 1
        if space_counter == 1:
            ...
        elif space_counter == 2:
            ...
            space_counter = 1

The "counter" starts at 0. At the first space, it increments to 1 and one action is performed. At the second and any subsequent space, it increments to 2 and is immediately reset to 1. Since it can only take on the values 0, 1 or 2, it is not really a counter.

It appears you are trying to do something different on the first space verses any subsequent space. A boolean "flag" is more descriptive in these cases:

seen_space = False
for ...:
    if char == " ":
        if not seen_space:
            ...
            seen_space = True
        else:
            ...

temp, a_str, and b_str are all similarly not descriptive variable names. final_str seems more descriptive, but it is used in statements like final_str = temp + " " + final_str, which means its value is not really "final", so again, it is not the best name either.

Iteration

for index in range(len(str1)):
    char = str1[index]
    ...

Using range(len(...) in a for loop is frowned upon in polite Python circles. If index is required in the body of the loop, enumerate(...) is preferred:

for index, char in enumerate(str1):
    ...

Special cases

elif index == len(str1) - 1 is executed on every non-space iteration of the loop. If your string is very, very long, this could be a source of inefficiency. It is testing for the end of the string, which happens at the end of the loop. Why not move this end-of-loop code out of the loop?

for index in range(len(str1)):
    ...
    if char == " ":
        ...
    else:
        temp += char

if temp != "":
    if final_str != "":
        final_str = temp + " " + final_str
    else:
        final_str = temp

Iteration (reprise)

By removing the index == len(str1) - 1 test in the loop body, we find we no longer need the index variable at all, so enumerate(...) is unnecessary, and the for loop can be simplified further:

for char in sentence:
    ...

Special cases (reprise)

Your code handles (and my above modification) has to handle the special case of a single word separately from multiple words. The reason is words end both with a subsequent space AND at the end of the string. We could work around this by intentionally adding a space at the end of the string ourselves, before processing begins.

str1 += " "

This additional sentinel guarantees words will always end with a space, and simplifies the code in the loop. Minor additional processing at the end may be necessary to remove the extra space in the output, depending on the exact implementation.

Answer 2

Not wanting to repeat what AJNeufeld has already said, I was curious how long it would take your code to reverse the full text of Moby Dick. While running this experiment, I noticed some funny behavior with spaces. For example, when your code is given " " (3 spaces), it returns " " (two spaces).

You might consider trying some quick tests such as these:

assert reverse_string("Happy new year! 2022") == "2022 year! new Happy"
assert reverse_string(" ") == " "
assert reverse_string("   ") == "   "
assert reverse_string(" a") == "a "
assert reverse_string("a ") == " a"
assert reverse_string(" a ") == " a "
assert reverse_string(" a  bc ") == " bc  a "
assert reverse_string("nospacesinthisone") == "nospacesinthisone"

On my computer, by the way, your approach handles Moby Dick in about 14 seconds! When I initially tried to refactor your code, I achieved a similar result:

Refactor Attempt #1: 13-14 seconds

def reverse_string(string: str) -> str:
    """Reverse the words of a string.

    >>> reverse_words('Happy new year! 2022')
    '2022 year! new Happy'
    """
    new_string, word = "", ""
    for char in string:
        if char == " ":
            new_string = char + word + new_string
            word = ""
        else:
            word += char
    n_missing_chars = len(string) - len(new_string)
    if n_missing_chars != 0:
        new_string = string[-n_missing_chars:] + new_string
    return new_string

Eventually, as you'll see below (if you try it), I managed to reduce the time to 0.1 seconds. It seems driven by replacing new = c + w + new with new += w + c. That this change would make things faster doesn't feel surprising, but I don't truly understand what is happening differently behind the scenes.

Refactor Attempt #2: 0.1 seconds

def reverse_string(string: str) -> str: 
    """Reverse the words of a string.

    >>> reverse_words('Happy new year! 2022')
    '2022 year! new Happy'
    """
    new_string, word = "", ""
    for char in reversed(string):
        if char == " ":
            new_string += word[::-1] + char
            word = ""
        else:
            word += char
    n_missing_chars = len(string) - len(new_string)
    if n_missing_chars != 0:
        new_string += string[:n_missing_chars]
    return new_string

While still adhering to your constraints, I wonder if there is a way to achieve similar or better performance than this without iterating through the string backwards.

Code Snippet: Trying Moby Dick yourself

If you want to reproduce the Moby Dick test yourself, you can use this snippet. You will need to save the full text of Moby Dick as a text file in the same directory as your Python script.

import time


with open("moby_dick.txt", "r") as f:
    string = f.read()

start = time.time()
reversed_moby_dick = reverse_string(string)
end = time.time()
print(f"Execution time: {end - start: .1f} seconds")

As a final comment, were it not for your rules about "built-in functions of string", I likely would have tried using str.join at some point.

This has been a very fun exercise. Thank you for posting it!

Answer 3

Avoid string concatenation in a loop

String concatenation in a loop is slow, because it involves in each iteration:

• memory allocation
• memory copy

As the concatenated string grows longer, the above just gets worse.

Reversing in-place

When reversing a list, it's most efficient to do it in place.

Consider a function to reverse a valid range in a list:

from typing import List


def reverse_range(items: List[any], start: int, end: int):
    left = start
    right = end - 1
    while left < right:
        items[left], items[right] = items[right], items[left]
        left += 1
        right -= 1

A nice trick

One obvious way to reverse words in a sentence might be to collect the words into a stack, and then pop the words into the reversed sentence.

Another way I find interesting:

• Reverse the characters of each word
• Reverse the entire range

Like this:

def reverse_sentence(s):
    chars = [c for c in s]
    index = start = 0
    while index < len(chars):
        c = chars[index]
        if c == ' ':
            reverse_range(chars, start, index)
            start = index + 1

        index += 1

    reverse_range(chars, start, len(chars))
    reverse_range(chars, 0, len(chars))

    return ''.join(chars)