Two out of three problems involve reversing today hence the title.
It’s also warmer than yesterday and my cold has passed .. onto to my fiancée (sorry).
Problem: Reverse the words of a string
N while preserving the word order.
'Apple two' => 'owt elppA'
This solution came to me pretty quickly. I was able to use some ideas from previous problems that were fresh in my head.
class Solution: def reverseWords(self, s): """ :type s: str :rtype: str """ return ' '.join(reversed(s[::-1].split(' ')))
Space complexity: I’m not sure. Depending on the implementation, I believe that it will mimic the runtime complexity.
Problem: Sort array
N so that the even indices have even numbers and the odd indices have odd numbers.
This is the next version of the first problem I solved yesterday.
class Solution: def sortArrayByParityII(self, A): """ :type A: List[int] :rtype: List[int] """ even = 0 odd = 1 ans =  * len(A) for i in A: if i % 2 == 0: ans[even] = i even += 2 else: ans[odd] = i odd += 2 return ans
Although it didn’t feel too bad writing this one out, I knew it was sub-optimal and could be done without that extra list.
Runtime complexity is
O(n) as its just one pass through.
Space complexity is
O(2n) which becomes
I looked up some solutions where it was solved in-place without additional data structures so that in future problems I’ll have a better idea of where to head. They involved managing two pointers for even and odd and being lazy about swapping. In my solution, a perfectly sorted list (to the problem spec) would be resorted regardless.
Problem: Reverse a string
I’ll be kicking myself later on that I chose to solve these easy ones now — assuming I can stick to my three per day target.
class Solution: def reverseString(self, s): """ :type s: str :rtype: str """ return s[::-1]
Linear complexity all around. Thank you Python for your terseness.
See you tomorrow.
Comments or questions? I enjoy talking with readers over email.