Sponsored
Sponsored
This approach involves splitting the original string into individual words using space as a delimiter, reversing the list of words, and then joining them back together with a single space.
Time Complexity: O(N), where N is the length of the string, as we process each character once.
Space Complexity: O(N), additional space for intermediate and result storage.
1#include <iostream>
2#include <sstream>
3#include <vector>
4#include <algorithm>
5
6std::string reverseWords(std::string s) {
7 std::stringstream ss(s);
8 std::string word;
9 std::vector<std::string> words;
10
11 while (ss >> word) {
12 words.push_back(word);
13 }
14 std::reverse(words.begin(), words.end());
15 std::string result;
16
17 for (const std::string& w : words) {
18 if (!result.empty()) {
19 result += " ";
20 }
21 result += w;
22 }
23 return result;
24}
25
26int main() {
27 std::string input = " hello world ";
28 std::string output = reverseWords(input);
29 std::cout << output << std::endl;
30 return 0;
31}This C++ solution utilizes the stringstream to extract words and stores them in a vector. It then reverses the vector and constructs the result string by iterating through the reversed vector.
This optimized approach manipulates the string in place by using a character array. We'll first reverse the entire string, and then reverse each word to return them to their correct order.
Time Complexity: O(N), where N is the number of characters in the string.
Space Complexity: O(1), as the operation is done in-place without extra space.
1
This C solution reverses the string in place using a helper function reverseCharArray. It then iterates over the string, reversing individual words and reconstructing the string without additional leading or trailing spaces.