Reverse Words in a String

MEDIUM

Description

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.

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: If the string data type is mutable in your language, can you solve it in-place with O(1) extra space?

Approaches

Checkout 3 different approaches to solve Reverse Words in a String. Click on different approaches to view the approach and algorithm in detail.

Using Language Built-in Functions

This approach leverages the built-in functions provided by the programming language, such as trim, split, and join, along with collection reversal utilities. It's often the most concise and readable solution for this problem.

Algorithm

Remove leading and trailing whitespace from the input string s using trim().
Split the trimmed string by one or more spaces ("\\s+") to get an array of words.
Create a List from the array of words to use the Collections.reverse() utility.
Reverse the order of elements in the list.
Join the words in the reversed list with a single space separator using String.join() to form the final string.

The simplest way to solve this problem is by using high-level, built-in string and collection manipulation functions. The process is straightforward:

Trim: The input string s can have leading or trailing spaces. s.trim() removes these.
Split: The trimmed string is then split into words. The key is to use a regular expression like "\\s+" as the delimiter, which handles cases with multiple spaces between words, treating them as a single separator.
Reverse: The resulting array of words is converted to a list, which is then reversed using Collections.reverse().
Join: Finally, String.join(" ", words) concatenates the elements of the reversed list into a single string, with each word separated by a single space.

import java.util.Arrays;
import java.util.Collections;

class Solution {
    public String reverseWords(String s) {
        // 1. Trim leading and trailing spaces
        String trimmedStr = s.trim();

        // 2. Split by one or more spaces
        String[] words = trimmedStr.split("\\s+");

        // 3. Reverse the array of words
        Collections.reverse(Arrays.asList(words));

        // 4. Join the words with a single space
        return String.join(" ", words);
    }
}

Complexity Analysis

Time Complexity: O(N)Space Complexity: O(N)

Pros and Cons

Pros:

Very simple and concise, leading to highly readable code.
Leverages optimized and well-tested library functions, reducing the chance of bugs.

Cons:

Creates intermediate data structures (an array of strings and a list), which can consume significant memory, making it O(N) in space complexity.
May not be allowed in interviews that restrict the use of certain built-in functions to test fundamental algorithm knowledge.

Code Solutions

Checking out 4 solutions in different languages for Reverse Words in a String. Click on different languages to view the code.

public class Solution {
    public string ReverseWords(string s) {
        return string.Join(" ", s.Trim().Split(" ").Where(word => !string.IsNullOrEmpty(word) && !string.IsNullOrEmpty(word.Trim())).Reverse());
    }
}

Video Solution

Watch the video walkthrough for Reverse Words in a String

Patterns:

Two Pointers

Data Structures:

String

Companies:

Accenture |Capgemini |Cisco |Deloitte |