# Python - use reverse() and reversed()

• ``````class Solution(object):
def reverseWords(self, s):
"""
:type s: a list of 1 length strings (List[str])
:rtype: nothing
"""
s.reverse()

index = 0
for i in range(len(s)):
if s[i] == " ":
s[index: i] = reversed(s[index: i])
index = i + 1

s[index: ] = reversed(s[index: ])
``````

Learn something new. Slice of list can use reverse() function, does not work. But, we can assign the reversed part to the slice of list.

• can you analyze the complexity? brilliant solution, btw

• At first, I got wrong comprehension about 's' type. It's good to know the operation of reverse slice of list

• @bearkino Unfortunately list slicing is O(n). So your solution is not really O(n) overall. This below is "real" O(n) time, O(1) space.

``````class Solution(object):
def reverseWords(self, s):
def reverse(i, j):
while 0 <= i < j < len(s):
s[i], s[j] = s[j], s[i]
i, j = i + 1, j - 1

s.append(" ")
start = 0
for i, v in enumerate(s):
if v == " ":
reverse(start, i - 1)
start = i + 1
s.pop()
reverse(0, len(s) - 1)

``````

• @bearkino Unfortunately list slicing is O(n). So your solution is not really O(n) overall.

I think you're wrong. The solution looks like O(n) to me. And your reasoning doesn't make sense.

• @bearkino Unfortunately list slicing is O(n). So your solution is not really O(n) overall.

I think you're wrong. The solution looks like O(n) to me. And your reasoning doesn't make sense.

When you do `reversed(s[index: i])` you are slicing, right?

• @agave Yes. So?

• @StefanPochmann Slicing is O(n), isn't it? Doesn't it create extra space too?

• @agave Yes, though in that case it's also O(i - index).

• @agave I think the solution is O(n), and yes, it creates extra space. reversed() return a reverse iterator.

• @bearkino The problem requires constant space right?

• I think @agave is correct. https://wiki.python.org/moin/TimeComplexity Each iteration of the for loop will perform operation that is dependent on N

• @agave Yes. Just like I said in the content, just try something new.

• @johnshiver Ok. What do you think about the time complexity?
What I think is:

1. s.reverse() - O(n)
2. for loop - O(n)
[ I don't think the reversed() inside and outside the loop should be added to calculate the time complexity]

So, to me it is still O(n).

• @agave That "Could you..." doesn't sound like a "requirement" to me but just like a "would be nice to have but isn't necessary". I think it's at least legitimate to interpret it that way.

• @bearkino What do you mean with not adding reversed() in the calculation? You can't just ignore it.

• @StefanPochmann You're right, but here we all like to challenge ourselves :)

• @agave Well I'd say if taking more freedom doesn't have any advantage or anything interesting, then it's indeed not worth showing. But if it does, then it might be. And I'd say it does look better than writing an extra reverse function yourself.

Do you agree by now that the solution is O(n) time?

• @StefanPochmann Yeah, I was agreeing also before :)

• @StefanPochmann I think I should say the adding reversed() in the calculation will be 1 when we find the limit of the f(x).
In this puzzle, the length of the words should have an upper bound. If there is no upper bound, the time complexity should be different.

f(x) = n1 + ny + y = (1+y)n + y (y is the average length of words)
limit f(x) = n (cause y could be treated like a constant number when n is going to infinity.)

Then, I got O(n).

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.