4
\$\begingroup\$

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")
\$\endgroup\$
  • \$\begingroup\$ so we expect 'eipupla' as the output for this function. \$\endgroup\$ – NinjaG Jul 23 '18 at 19:39
5
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ Even if it's not in OP's code, I would suggest to ''.join before returning. \$\endgroup\$ – 409_Conflict Nov 18 '16 at 8:05
  • \$\begingroup\$ @MathiasEttinger Yeah that's probably a good idea, I'll add that now, thanks :) \$\endgroup\$ – Peilonrayz Nov 18 '16 at 8:45
  • \$\begingroup\$ I liked this one. I am also glad that I wasn't so far off :D \$\endgroup\$ – theMarceloR Nov 22 '16 at 20:28
  • \$\begingroup\$ minimum space + optimal time complexity + readability \$\endgroup\$ – NinjaG Jul 23 '18 at 19:39
2
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

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).

\$\endgroup\$
  • 1
    \$\begingroup\$ Don't forget strings are immutable internally, and so new_word += letter is \$O(n)\$, not \$O(1)\$. :) \$\endgroup\$ – Peilonrayz Nov 18 '16 at 8:56
  • \$\begingroup\$ 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 ...). \$\endgroup\$ – 409_Conflict Nov 18 '16 at 8:56
  • \$\begingroup\$ @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 :-) \$\endgroup\$ – ChatterOne Nov 18 '16 at 9:02
  • \$\begingroup\$ @ChatterOne Fair dues, :) But, you should probably mention the performance concern just for people that don't know \$\endgroup\$ – Peilonrayz Nov 18 '16 at 9:05
  • \$\begingroup\$ Thanks for pointing that out. I also got eipupla as the result \$\endgroup\$ – NinjaG Jul 23 '18 at 19:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.