function that reverses a string every time a vowel appears in it?

user_18718014 0
Viewed 124

I'm trying to make a function that, for every occurrence of a vowel in a string, reverses said-string (and includes the vowel when it does this). The function is somewhat complex for my understanding so I'd like some help and a maybe a breakdown of it. However, I would only like to use the operators and statements that I'm currently learning (for/while and if). If possible, I would also like to avoid using list comprehension.

Here's what the inputs and outputs should look like:

an example input would be reverse_per_vowel('aerith') which returns 'iraeth'

If we break the process of this function into steps, it should look like:

(a)erith → (a)erith (the first letter is a vowel, so it is reversed. However, because it is the first letter in the string, there are no visible changes.)

(ae)rith → (ea)rith (the second letter is also a vowel, so every letter in the string leading up to and including the vowel is reversed.)

(eari)th → (irae)th (the fourth letter is a vowel, so everything leading up to and including it is also reversed. Note how it accounts for the letters in the string that were reversed previously.)

as you can see, the amount of times the string is reversed is cumulative and I'm not quite sure how to code for this. However, I've attempted to write a component of the function.

What I'm trying

vowellist = 'aeiouAEIOU'
sampleword = 'aerith'

indexlist = []
for i in range(len(sampleword)):
    if sampleword[i] in vowel_list:
        indexlist.append(i)
indexlist

output: [0, 1, 3]

this excerpt does not reverse any parts of the string, however it returns indexes where the string should be reversed. What I planned on doing was plugging these indexes back into the sample word somehow and using [::-1] to reverse a portion of the string. However, I don't know how I would do this nor if it would be a good idea. Any help would be appreciated.

if-statement for-loop function python
4 Answers

If there are many vowels, then the repeated reversals seem like they could be avoided, as a second reversal somewhat is an undo of the previous reversal.

And yes, you could use this algorithm:

  • Build two strings. They start emtpy, and mark the second of them as the "active" one.

  • Visit the input characters in reversed order: from last to first

    • As long as they are consonants add them to the currently active string
    • When it is a vowel, switch the active string to be the other one, and add the vowel there

  • At the end of this process, reverse the second string and return the concatenation of the two strings:

VOWELS = set("aeiouAEIOU")

def reverse_per_vowel(s):
    endings = ["", ""]
    side = 1
    for c in reversed(s):
        if c in VOWELS:
            side = 1 - side  # Toggle between 0 and 1
        endings[side] += c
    return endings[0] + endings[1][::-1]

As this algorithm is not reversing each time it meets a vowel, but only performs one reversal at the end, it runs with linear time complexity, contrary to what you would get if you implement the described process literally, which has a worst case time complexity of O(n²).

With this complexity analysis I assume that extending a string with a character is a constant time process. If there is doubt about this, then implement it with two lists of characters, calling append and perform a join at the end of the process to get the final string:

VOWELS = set("aeiouAEIOU")

def reverse_per_vowel(s):
    endings = [[], []]
    side = 1
    for c in reversed(s):
        if c in VOWELS:
            side = 1 - side  # Toggle between 0 and 1
        endings[side].append(c)
    
    return "".join(endings[0] + endings[1][::-1])
user_54598390

One easy way to achieve this is to use recursion:

vowels = set('aeiouAEIOU')

def reverse_per_vowel(s):
    if not s: # empty string
        return ''
    beforelast, last = s[:-1], s[-1]
    if last in vowels:
        return last + reverse_per_vowel(beforelast)[::-1]
    return reverse_per_vowel(beforelast) + last

print(reverse_per_vowel('aerith')) # iraeth
user_114508200

You can do it with simple modification of your for loop and some advanced slicing:

vowellist = 'aeiouAEIOU'
sampleword = 'aerith'

for i in range(len(sampleword)):
    if sampleword[i] in vowellist:
        sampleword = sampleword[i::-1] + sampleword[i + 1:]

print(sampleword)

Every iteration if vowel appears you can just reassign string with new partly reversed. Output:

iraeth

You can help my country, check my profile info.

user_108244070

Using a list makes it very easy and clean:

def reverse_per_vowel(word):
    result = []
    for letter in word:
        result.append(letter)
        if letter in 'aeiouAEIOU':
            result.reverse()
    return ''.join(result)

It's also fast. For your sample word, it was faster than all the other solutions posted so far, and for a word with 1000 letters ('aerith' * 167), only @trincot's second solution was a bit faster, the others were 2 to 10 times slower. Eventually of course it really loses to trincot's second solution, which at 10,000 letters was about 5 times faster and at 100,000 letters was about 46 times faster.

And here's another linear-time one, a bit faster than trincot's (tested on strings with up to a million letters). It puts the letters into a deque so it can efficiently append to the left or to the right. And it has a flag that tells whether the result is currently in reverse.

from collections import deque

def reverse_per_vowel(word):
    result = deque()
    reverse = False
    for letter in word:
        if not reverse:
            result.append(letter)
        else:
            result.appendleft(letter)
        if letter in 'aeiouAEIOU':
            reverse = not reverse
    if reverse:
        result.reverse()
    return ''.join(result)
user_126710570
Related