0186-reverse-words-in-a-string-ii

Try it on leetcode

Description

Given a character array s, reverse the order of the words.

A word is defined as a sequence of non-space characters. The words in s will be separated by a single space.

Your code must solve the problem in-place, i.e. without allocating extra space.

 

Example 1:

Input: s = ["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"]
Output: ["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"]

Example 2:

Input: s = ["a"]
Output: ["a"]

 

Constraints:

• 1 <= s.length <= 105
• s[i] is an English letter (uppercase or lowercase), digit, or space ' '.
• There is at least one word in s.
• s does not contain leading or trailing spaces.
• All the words in s are guaranteed to be separated by a single space.

Solution(Python)

class Solution:
    def reverseWords(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        if s is None:
            return
        s.reverse()
        
        n = len(s)
        i = 0
        j = 0
        
        while i< n and j<n:
            # swap word
            while j <n and s[j] != " " :
                j+=1
            k = i
            l = j - 1
            
            while k < l and l < n:
                s[k],s[l] = s[l],s[k]
                k+=1
                l-=1
            #next word
            i = j +1
            j+=2