Given a string s, reverse every word individually. The spaces should remain in the same positions, and the order of words should not change. A word is a continuous group of non-space characters.
Example 1
Input: s = "hello world"
Output: "olleh dlrow"
Explanation: hello becomes olleh, and world becomes dlrow.
Example 2
Input: s = " DSA is fun "
Output: " ASD si nuf "
Explanation: Each word is reversed, but leading, trailing, and multiple spaces remain unchanged.
Brute Approach
A stack naturally reverses things because the last character pushed comes out first. For each word, push its characters into a stack. When a space is found, pop all characters from the stack and add them to the answer. This reverses the current word. This is mostly an educational variation of brute force. It teaches the reverse behavior nicely, but it still uses extra space.
Algorithm
Traverse the string from left to right and push non-space characters into a stack.
When a space is found, pop all characters from the stack into the answer. This reverses the word that just ended.
Add the space directly to the answer so the original spacing is preserved.
After traversal, pop the remaining characters from the stack because the last word may not be followed by a space.
Dry Run
Reverse Each Word in a String Brute Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* Reverses every word using a stack while keeping word order and spaces unchanged. */ string reverseEveryWord(string s) { /* The stack stores characters of the current word so they can be removed in reverse order. */ stack<char> st; /* This stores the final string after reversing each word individually. */ string result = ""; for (int i = 0; i < s.length(); i++) { /* Non-space characters belong to the current word, so they are pushed into the stack. */ if (s[i] != ' ') { st.push(s[i]); } else { /* A space means the current word has ended, so all stacked characters are added back reversed. */ while (!st.empty()) { result += st.top(); st.pop(); } result += s[i]; } } /* The last word may not be followed by a space, so remaining characters must also be added. */ while (!st.empty()) { result += st.top(); st.pop(); } return result; }};int main() { // Driver code starts string s = " DSA is fun "; Solution sol; cout << sol.reverseEveryWord(s); return 0;}Complexity Analysis
Time Complexity: O(n) because each character is pushed and popped at most once.
Space Complexity: O(n) because the answer string is created, and the stack may store characters of a word.
Optimal Approach
A word is just a range inside the string. If the start and end index of a word are known, the word can be reversed by swapping characters from both ends. Spaces do not need any work. They only tell where one word ends and another begins. So the idea is to scan the string, find each word range, and reverse that range in place.
In C++, strings are mutable, so this can be done directly. In Python, Java, and JavaScript, strings are immutable, so the string is first converted into a character list or array.
Algorithm
Convert the string into a mutable character array if the language needs it. This allows characters to be swapped.
Start scanning from index
0. If the current character is a space, move ahead because spaces must stay unchanged.When a non-space character is found, mark it as the start of a word. Then move forward until a space or the end of the string is reached.
Reverse the characters from the word’s start index to its end index. This flips only the current word.
Continue scanning until the whole string is processed.
Dry Run
Reverse Each Word in a String Optimal Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {private: /* Reverses characters between left and right index inside the same string. */ void reverseRange(string& s, int left, int right) { while (left < right) { swap(s[left], s[right]); left++; right--; } }public: /* Reverses every word in the string while keeping word order and spaces unchanged. */ string reverseEveryWord(string s) { int n = s.length(); int i = 0; while (i < n) { /* Spaces are skipped because they must remain at the same positions in the final string. */ if (s[i] == ' ') { i++; } else { /* This marks the first character of the current word. */ int start = i; while (i < n && s[i] != ' ') { i++; } /* i is now one step after the word, so the last character is present at i - 1. */ int end = i - 1; reverseRange(s, start, end); } } return s; }};int main() { // Driver code starts string s = " DSA is fun "; Solution sol; cout << sol.reverseEveryWord(s); return 0;}Complexity Analysis
Time Complexity: O(n) because each character is scanned and swapped at most once.
Space Complexity: O(1) in languages with mutable strings or character arrays. In Python, Java, and JavaScript, it is O(n) because strings must be converted into a mutable character array.
Interview follow-up Questions
No. Spaces should stay exactly as they are unless the problem statement says otherwise.
Be the first to add a comment.