DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Reverse Words in a String

mediumStrings

Problem statement

Given a string s, return its words in reverse order. A word is a run of non-space characters. The input may have leading spaces, trailing spaces, or several spaces between words; the output must have exactly one space between words and none at either end. The characters inside each word keep their order. s contains at least one word.

Examples

Example 1

Input: s = " pull build deploy "

Output: "deploy build pull"

Explanation: The three words are reversed, and the extra spaces are dropped.

Example 2

Input: s = "one"

Output: "one"

Hints

Approach

Work on a mutable character buffer with no word list. This is the version asked for when the interviewer says "do it in place".

  1. Reverse the whole buffer. The words are now in the right order, but each is spelled backwards.
  2. Scan with a read index and a write index. Skip spaces. Before copying each word (except the first), write a single space. Copy the word's characters forward to the write position.
  3. Reverse just the word you copied, which restores its spelling.
  4. The first write characters are the answer.

The write index never passes the read index, so copying forward is always safe. Strings are immutable in Python and Java, so the buffer itself is a copy of the input; beyond that buffer the extra space is O(1). In C or C++ the same code runs directly on the input.

ComplexityTime O(n)Space O(1) extra
Python
class Solution:
def reverseWords(self, s: str) -> str:
buf = list(s)
buf.reverse() # words in the right order, each spelled backwards
def flip(lo: int, hi: int) -> None:
while lo < hi:
buf[lo], buf[hi] = buf[hi], buf[lo]
lo += 1
hi -= 1
n, read, write = len(buf), 0, 0
while read < n:
if buf[read] == " ":
read += 1
continue
if write > 0:
buf[write] = " " # single space between words
write += 1
start = write
while read < n and buf[read] != " ":
buf[write] = buf[read]
write += 1
read += 1
flip(start, write - 1) # restore this word's spelling
return "".join(buf[:write])

Follow-up questions

  • Reverse the labels of a dotted hostname (web.eu.example.com to com.example.eu.web).
  • Rotate the words of a sentence left by k positions in place.

Frequently asked questions

With no argument, split() splits on runs of whitespace and drops empty strings. With " ", every single space is a separator, so "a b" gives ['a', '', 'b'] and the output would contain extra spaces.

Start with split, reverse and join, and say it is O(n) time and space. If asked for constant extra space, explain the reverse-everything-then-reverse-each-word trick.

Cleaning up whitespace in fields pulled from command output, where columns are padded with a variable number of spaces, and reordering tokens, such as turning a.b.example.com into com.example.b.a for sorting DNS names by zone.