algoadvance

Leetcode 151. Reverse Words in a String

Problem Statement

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.

Example:

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

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

Input: "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.

Clarifying Questions

  1. Input Constraints:
    • Is the input string s guaranteed to be non-empty? (Typically, it could be empty so assume it can be.)
    • Can we consider special characters within words?
    • Should we handle tabs or newlines, or is it guaranteed to only contain spaces for separation?
  2. Output Requirements:
    • Is there any specific constraint on the length of the output string?

Strategy

  1. Trim Leading/Trailing Spaces: First, we will trim any leading or trailing spaces from the input string.
  2. Split Words: We will split the string by spaces into individual words.
  3. Reverse Words: We will reverse the order of these words.
  4. Join Words: Finally, we will join these reversed words with a single space to form the final reversed string.

Code

Here’s the implementation in C++:

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

std::string reverseWords(std::string s) {
    // Trim leading and trailing spaces
    s.erase(s.begin(), std::find_if(s.begin(), s.end(), [](int ch) {
        return !std::isspace(ch);
    }));
    s.erase(std::find_if(s.rbegin(), s.rend(), [](int ch) {
        return !std::isspace(ch);
    }).base(), s.end());

    std::istringstream stream(s);
    std::string word;
    std::vector<std::string> words;

    // Split by space and store words in the vector
    while (stream >> word) {
        words.push_back(word);
    }

    // Reverse the vector of words
    std::reverse(words.begin(), words.end());

    // Join words with a single space
    std::ostringstream reversedStream;
    for (size_t i = 0; i < words.size(); ++i) {
        if (i != 0) {
            reversedStream << " ";
        }
        reversedStream << words[i];
    }

    return reversedStream.str();
}

int main() {
    std::string s = "  the sky is blue  ";
    std::cout << "\"" << reverseWords(s) << "\"" << std::endl;
    return 0;
}

Time Complexity

So, the total time complexity is (O(n)), where (n) is the length of the input string.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI