Reverse vowels in a string

Question

What do you think about this solution? I guess there are too many lists...

vowels = "aeiou"
def reverseVowels(string):
 vowels_list = []
 string_list = list(string)
 for index,letter in enumerate(string_list):
 if letter in vowels:
 vowels_list.append(letter)
 reversed_vowels_list = list(reversed(vowels_list))
 new_string_list = list(string_list)
 for index,vowel in enumerate(vowels_list):
 idx_vowel_in_string = string_list.index(vowel)
 new_string_list[idx_vowel_in_string] = reversed_vowels_list[index]
 print new_string_list
reverseVowels("aupiple")

• NinjaG: so we expect 'eipupla' as the output for this function.

Answer 1

You use for index, letter in enumerate(string_list): but don't use the index. Instead of using string_list.index(vowel) in the second loop you can instead build an index list in the first loop. And reverse either the index list or the vowels list. This should have a better time complexity as string_list.index(vowel) seems to be making your code time complexity \$O(n^2)\$.

I'd also change your code to follow PEP8, and remove all the redundant _list parts in your variable names. As this makes your code easier to read.

Finally I'd return, rather than print, the final list as it makes the code more reusable. And, as Mathias commented, you could also change your return type to a string, as giving a string as input and getting a list of strings as output is a little odd.

VOWELS = set('aeiou')
def reverse_vowels(string):
 string = list(string)
 vowels = []
 indexes = []
 for index, letter in enumerate(string):
 if letter in VOWELS:
 vowels.append(letter)
 indexes.append(index)
 for i, char in zip(indexes, reversed(vowels)):
 string[i] = char
 return ''.join(string)

• 301_Moved_Permanently: Even if it's not in OP's code, I would suggest to ''.join before returning.
• Peilonrayz: @MathiasEttinger Yeah that's probably a good idea, I'll add that now, thanks :)
• theMarceloR: I liked this one. I am also glad that I wasn't so far off :D
• NinjaG: minimum space + optimal time complexity + readability
• Aivar Paalberg: I personally wouldn’t use "string" as a name of a list.

Answer 2

Lets have a look at the algorithm you are using, and see if we can tweak it.

First you get each vowel. Then you reverse the list Finally you get the index of each vowel and replace it with the next vowel in the list.

There is a bug here, list.index will return the index of the first occurrence of a vowel, so if you replace the word with "aapiple" you will see the bug in action.

The main area of interest is getting the index of each vowel, so lets do that.

vowel_indexes = [index for index, letter in enumerate(s) if letter in vowels]

With the indexes, we can just swap the character at the first index, with the character at the last index. As a result we can avoid iterating with two pointers over the whole list again, we only need to go halfway with each one. (Small note, we don't need to swap the middle vowel if there are an odd amount of them, since it will just replace itself.)

 halfway_point = len(vowel_indexes)/2
 first_half = vowel_indexes[:halfway_point]
 second_half = reversed(vowel_indexes[halfway_point:])
 new_word = list(s)
 for i, j in zip(first_half, second_half):
 new_word[i], new_word[j] = new_word[j], new_word[i]

And since we were given a string, it would be nice to return a string

return "".join(new_word)

---

The final code looks like this:

vowels = "aeiou"
def reverseVowels(s):
 vowel_indexes = [index for index, letter in enumerate(s) if letter in vowels]
 halfway_point = len(vowel_indexes)/2
 first_half = vowel_indexes[:halfway_point]
 second_half = reversed(vowel_indexes[halfway_point:])
 new_word = list(s)
 for i, j in zip(first_half, second_half):
 new_word[i], new_word[j] = new_word[j], new_word[i]
 return "".join(new_word)

Answer 3

You're using a lot of indexes, while you actually only need one (well, one index plus a generator).

I think this is more readable:

vowels = 'aeiou'
def get_reversed_vowel(input_string):
 for letter in input_string[::-1]:
 if letter in vowels:
 yield(letter)
def reverseVowels(input_string):
 reversed_vowel = get_reversed_vowel(input_string)
 new_word = ''
 for letter in input_string:
 if letter in vowels:
 new_word += reversed_vowel.next()
 else:
 new_word += letter
 return new_word
print reverseVowels('applepie')

EDIT: As @Perilonrayz said, there is a performance hit because of immutability of strings. You'll probably only notice this for large-ish input, but still (I quote):

Don't forget strings are immutable internally, and so new_word += letter is O(n), not O(1).

• Peilonrayz: Don't forget strings are immutable internally, and so new_word += letter is \$O(n)\,ドル not \$O(1)\$. :)
• 301_Moved_Permanently: You can easily turn the if into a ternary statement and thus see that you: new_word = ''; for ...: new_word += <xxx> which is inneficient compared to ''.join(<xxx> for ...).
• ChatterOne: @Peilonrayz and Mathias Ettinger : yes, you're both correct, of course. But as I said, I think this code is more readable, not more performant :-)
• Peilonrayz: @ChatterOne Fair dues, :) But, you should probably mention the performance concern just for people that don't know
• NinjaG: Thanks for pointing that out. I also got eipupla as the result