algoadvance

Leetcode 557. Reverse Words in a String III

Problem Statement

You are given a string s. The string contains words separated by spaces. Each word consists of English letters (lower-case and upper-case). You need to return a string where the letters of each word are reversed, but the words themselves remain in the original order.

Example 1:

Input: s = "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"

Example 2:

Input: s = "God Ding"
Output: "doG gniD"

Note:

Clarifying Questions

  1. Are punctuation marks considered part of a word or should they be treated differently?
    • They are considered part of the word based on the example provided.
  2. Can extra spaces be present between words?
    • No, based on the problem statement, words are separated by a single space.
  3. Are there any constraints on the length of the string?
    • The problem does not explicitly mention constraints, so we assume it is manageable within standard memory limits.

Strategy

  1. Split the input string s into words using space as the delimiter.
  2. Reverse each word.
  3. Join the reversed words with a space to form the final string.

Code

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

std::string reverseWords(std::string s) {
    std::istringstream iss(s);
    std::string word;
    std::vector<std::string> words;
    
    // Split the string into words
    while (iss >> word) {
        // Reverse each word and store it in the vector
        std::reverse(word.begin(), word.end());
        words.push_back(word);
    }
    
    // Join reversed words with space
    std::ostringstream oss;
    for (size_t i = 0; i < words.size(); ++i) {
        if (i > 0) {
            oss << " ";
        }
        oss << words[i];
    }
    
    return oss.str();
}

int main() {
    std::string s = "Let's take LeetCode contest";
    std::string result = reverseWords(s);
    std::cout << result << std::endl; // Output: "s'teL ekat edoCteeL tsetnoc"
    
    return 0;
}

Time Complexity

  1. Splitting the string into words - O(n), where n is the length of the string as each character is processed once.
  2. Reversing each word - O(m) for each word where m is the length of the word. As the sum of all word lengths is equal to n, this step is O(n) in total.
  3. Joining the words back into a single string - O(n), where n is the length of the final string.

Overall, the time complexity of this solution 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