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).
- Reverse Words in a String III
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.
- Sort Array By Parity II
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 = 0odd = 1ans =  * len(A)for i in A:if i % 2 == 0:ans[even] = ieven += 2else:ans[odd] = iodd += 2return 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.
- Reverse String
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.