LeetCode: Reverse Words in a String II

Reverse Words in a String II

Similar Problems:

• Series: Reverse List/String & Follow-up
• CheatSheet: Leetcode For Code Interview
• CheatSheet: Common Code Problems & Follow-ups
• Tag: #reverseitem, #string

Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters.

The input string does not contain leading or trailing spaces and the words are always separated by a single space.

For example,

Given s = "the sky is blue",
return "blue is sky the".

Could you do it in-place without allocating extra space?

Update (2017-10-16):
We have updated the function signature to accept a character array, so please reset to the default code definition by clicking on the reload button above the code editor. Also, Run Code is now available!

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

## https://code.dennyzhang.com/reverse-words-in-a-string-ii
## Basic Ideas: two pointer
##
##  Double reverse
##
## Complexity: Time O(n), Space O(1)
class Solution:
    def reverseWords(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        def reverse(left, right):
            while left<right:
                s[left], s[right] = s[right], s[left]
                left, right = left+1, right-1

        reverse(0, len(s)-1)
        prev = 0
        for i in range(len(s)+1):
            if i == len(s) or s[i] == " ":
                reverse(prev, i-1)
                prev = i+1