Reverse Words in a String

Dec 18, 2024 • 4 mins read
Hero Image

Problem Overview

The LeetCode problem "Reverse Words in a String" asks you to take a given input string and reverse the order of the words. A word is defined as a sequence of non-space characters. The input string may contain leading or trailing spaces as well as multiple spaces between words. The expected output is a string with the words in reverse order, separated by a single space, and no leading or trailing spaces.

Example:

Input: "  hello world  "
Output: "world hello"

Understanding the Problem

The task is to reverse the order of words in a given string. The key challenges include handling multiple spaces and ensuring that the output string is properly formatted with single spaces separating words and no leading or trailing spaces. It's important to accurately identify and extract the words from the string while navigating and adjusting various space conditions.

Key DSA Concepts and Theory

To solve this problem, we rely on several fundamental concepts:

  • String Manipulation: Understanding how to navigate through and modify strings is crucial.
  • Trimming: Removing leading and trailing spaces to ensure the output is formatted correctly.
  • Splitting and Joining: Extracting words by identifying delimiters (spaces) and recombining them.
  • Data Structures: Using a stack or list to reverse the order of words efficiently.

String Manipulation

Strings in programming are often represented as an array of characters. We can utilize various methods to analyze and transform strings, such as trimming unwanted characters, splitting based on delimiters, and joining sequences.

Trimming

Trimming is the process of removing unwanted leading and trailing spaces in a string. This ensures that when we form the final output, there are no inappropriate spaces preceding or succeeding the main content.

Splitting and Joining

Splitting breaks down the string into a collection of words based on spaces, while joining allows us to reconstruct these pieces into a single string separated by a specified delimiter (in this case, a single space).

Solution Approach

Step-by-step Explanation

  1. Trim the Input String: Start by eliminating any leading and trailing spaces to simplify subsequent operations.

  2. Split the String into Words: Using spaces as the delimiter, decompose the cleaned-up string into individual components (words).

  3. Reverse the Order of Words: This can be achieved using a stack data structure or by straightforwardly reversing the list of words obtained in the previous step.

  4. Join the Words: Combine the words back into a single string with a single space between each word.

  5. Return the Result: The final string, now reversed with proper spacing, is returned as the output.

C++ Code Example

#include <iostream>
#include <vector>
#include <sstream>
#include <algorithm>

std::string reverseWords(const std::string &s) {
    std::istringstream iss(s);
    std::vector<std::string> words;
    std::string word;
    
    // Extract words
    while (iss >> word) {
        words.push_back(word);
    }
    
    // Reverse the words
    std::reverse(words.begin(), words.end());
    
    // Join them into a single string
    std::string result;
    for (size_t i = 0; i < words.size(); ++i) {
        if (i != 0) {
            result += " ";
        }
        result += words[i];
    }
    
    return result;
}

int main() {
    std::string input = "  hello world  ";
    std::cout << reverseWords(input) << std::endl;
    return 0;
}

Java Code Example

import java.util.*;

public class ReverseWords {

    public static String reverseWords(String s) {
        String[] words = s.trim().split("\\s+");
        Collections.reverse(Arrays.asList(words));
        return String.join(" ", words);
    }
    
    public static void main(String[] args) {
        String input = "  hello world  ";
        System.out.println(reverseWords(input));
    }
}

Time and Space Complexity Analysis

  • Time Complexity: O(n), where n is the length of the input string. Each character is visited a finite number of times.
  • Space Complexity: O(n), because the additional space is used to store the extracted words before reconstructing the final string.

Common Mistakes to Avoid

  • Handling Extra Spaces: Ensure that the final result does not contain extra spaces by carefully trimming and verifying delimiters.
  • Reversing Incorrectly: Remember that you must reverse the order of words, not their individual characters.
  • Mutability Issues: Be aware of the immutability of strings in languages like Java, which requires auxiliary space for modifications.

Similar Problems on LeetCode

  • 151. Reverse Words in a String
  • 186. Reverse Words in a String II
  • 558. Quad Tree Intersection

Additional Resources and References

Understanding how to transform strings by manipulating their structure and sequence is an invaluable skill in programming. This problem encourages a deeper grasp of text processing techniques, crucial for encountering various algorithmic challenges.