Why these two almost same codes have different efficient (Python)?

Question

I was practicing programming by Python on leetcode.

So this is the problem: https://leetcode.com/problems/reverse-vowels-of-a-string/

And this is my answer:

def reverseVowels(s):
    result = list(s)
    v_str = 'aeiouAEIOU'
    v_list = [item for item in s if item in v_str]
    v_list.reverse()
    v_index = 0
    for i, item in enumerate(s):
        if item in v_list:
            result[i] = v_list[v_index]
            v_index+=1
    return ''.join(result)

The result: Time Limit Exceeded

And I found an extremely similar answer in the discussion:

def reverseVowels(s):
    lst = list(s)
    vowels_str = "aeiouAEIOU"
    vowels_list = [item for item in lst if item in vowels_str]
    vowels_list.reverse()
    vowels_index = 0
    for index, item in enumerate(lst):
        if item in vowels_str:
            lst[index] = vowels_list[vowels_index]
            vowels_index += 1
    return ''.join(lst)

The result: Accepted

This is so weird. I think these two code seem exactly the same.

The difference of them is nothing but parameters.

I am curious about why these codes cause distinct results.

That's not python code. You cannot have a `return` outside a `def`. Please provide the **complete** definitions, including the parameter lists. Also: try to run the code multiple times... it's often the case that the code runs just as fast and passes the time limit only 50% of the time. — Bakuriu, May 16 '16 at 06:56
@Bakuriu Sorry, I miss some code before. Thank you for your reminding. I have tried my code lots of times. But it always give me the same result.. — Mars Lee, May 16 '16 at 07:01

score 3 · Accepted Answer · answered May 16 '16 at 07:07

There are two different lines between both codes. First one is:

for index, item in enumerate(lst):
for i, item in enumerate(s):

In the first case it iterates through the list and in the second it iterates through the string. There may be some performance loss here but it is not the main problem.

if item in vowels_str:
if item in v_list:

This is where the running time goes. In the first case (working code) it looks for the character in the string made of vowels, which has constant length. In the second case, it looks for the character in the list of all vowels contained in the string, which can be huge depending of the string given in test.

score 1 · Answer 2 · edited May 23 '17 at 12:08

In the first of these you are iterating over the string (s) directly, multiple times. In the second, after converting to a list, you are iterating over that list (lst).

The exact reason this causes a difference is an (admittedly large and probably important for correctness) implementation detail in the python interpreter.

See related question for more discussion: Why is it slower to iterate over a small string than a small list?

Why these two almost same codes have different efficient (Python)?

2 Answers2