Reverse a Sentence (Sentence Reversal Algorithm)

Given a list of strings sentence where each sentence[i] is a string with single character, reverse the order of the words in the sentence. You may assume there’s no extraneous spaces in the sentence. Can you do modify sentence in-place and solve in O(1) space?

Constraints
n ≤ 10,000 where n is the length of sentence.
Example 1
Input
sentence = [“h”, “i”, ” “, “w”, “o”, “r”, “l”, “d”]
Output
[“w”, “o”, “r”, “l”, “d”, ” “, “h”, “i”]

Reverse Words in Sentence

We can first reverse the entire sentence string by characters in O(N) time. After reversal, the words in the sentence are reversed which we need to revert them. The second pass will be checking the positions of the space (thus locating the left and right index of each word) and reversing them.

We can implement a function to reverse characters within a index range. The overall complexity is O(N^2).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution:
    def reverseSentenceByWords(self, sentence):
        def reverse(s, i, j):
            while i < j:
                s[i], s[j] = s[j], s[i]
                i += 1
                j -= 1
        reverse(sentence, 0, len(sentence) - 1)
        prev = 0
        for i, c in enumerate(sentence):
            if c == ' ':
                reverse(sentence, prev, i - 1)
                prev = i + 1
        reverse(sentence, prev, len(sentence) - 1)
        return sentence

class Solution:
    def reverseSentenceByWords(self, sentence):
        def reverse(s, i, j):
            while i < j:
                s[i], s[j] = s[j], s[i]
                i += 1
                j -= 1
        reverse(sentence, 0, len(sentence) - 1)
        prev = 0
        for i, c in enumerate(sentence):
            if c == ' ':
                reverse(sentence, prev, i - 1)
                prev = i + 1
        reverse(sentence, prev, len(sentence) - 1)
        return sentence

Alternatively, this can be solved by Python one-liner:

1
2
3

class Solution:
    def reverseSentenceByWords(self, sentence):
        return list(" ".join("".join(sentence).split()[::-1]))

class Solution:
    def reverseSentenceByWords(self, sentence):
        return list(" ".join("".join(sentence).split()[::-1]))

See also: How to Reverse Words in a String?

–EOF (The Ultimate Computing & Technology Blog) —