151. Reverse Words in a String

22.5%

Problem

Given an input string 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 at least one space.

Return a string of the words in reverse order concatenated by a single space.

Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

Example 1:

Input: s = "the sky is blue"
Output: "blue is sky the"

Example 2:

Input: s = "  hello world  "
Output: "world hello"
Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3:

Input: s = "a good   example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

Example 4:

Input: s = "  Bob    Loves  Alice   "
Output: "Alice Loves Bob"

Example 5:

Input: s = "Alice does not even like bob"
Output: "bob like even not does Alice"

Constraints:

1 <= s.length <= 10⁴
s contains English letters (upper-case and lower-case), digits, and spaces ' '.
There is at least one word in s.

Follow up:

Could you solve it in-place with O(1) extra space?

Discussion

The problem requires us to reverse the words in a sentence string. So we think of breaking down the string into words list, and perform reverse with two pointers.

Interesting that one solution in leetcode mentioned string.split() in python can remove all space, hence giving a more elegant solution.

Solution

We first break down the sentence into list of word by splitting, then we have two pointers from the beginning and end, iterating till they meet.

In each iteration, we check if any space is scanned and we will skip it, then we interchange the values at the two pointers, and update the two pointers after complete.

class Solution:
    def reverseWords(self, s: str) -> str:
        sl = s.split(' ')

        head = 0
        tail = len(sl) - 1

        while head <= tail:
            if sl[head] == '':
                sl.pop(head)
                tail -=1
                continue

            if sl[tail] == '':
                sl.pop(tail)
                tail -=1
                continue

            sl[head], sl[tail] = sl[tail], sl[head]
            head += 1
            tail -=1
            continue

        return ' '.join(sl)

Complexity Analysis

Time Complexity: O(n), scanning the string into words, and perform reverse with two pointers along the array.
Space Complexity: O(n), as we have to put the word array in memory.

LeetcodeCollection

151. Reverse Words in a String

Problem

Discussion

Solution

Complexity Analysis