Given a character array s, reverse the order of the words. A word is a group of characters without spaces. Every two words are separated by a single space.
The reversal must be performed in-place without using extra space.
Example 1
Input: s = ["c","o","d","i","n","g"," ","i","s"," ","f","u","n"]
Output: ["f","u","n"," ","i","s"," ","c","o","d","i","n","g"]
Explanation: The word order changes from “coding is fun” to “fun is coding.”
Example 2
Input: s = ["h","e","l","l","o"," ","w","o","r","l","d"]
Output: ["w","o","r","l","d"," ","h","e","l","l","o"]
Explanation: The word order changes from “hello world” to “world hello.”
Brute Force Approach
The most direct idea is to store all the words separately before rearranging the sentence. The character array is first converted into a string, and stringstream helps extract each word into a vector. Once all words are collected, traversing the vector from the end gives the words in reverse order while keeping the characters within each word unchanged.
The reversed words are then copied back into the original character array, with a single space inserted between consecutive words. This approach uses extra space for storing the temporary string and the vector of words.
Algorithm
Convert the character array into a temporary string.
Use
stringstreamto read the words and store them in a vector.Start from the last word and traverse the vector backwards.
Copy each word character by character into the original array.
Insert a single space between consecutive words.
Continue until all words have been copied back.
Dry Run
Reverse Words in a String II - Brute
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Reverses the order of words using extra space. void reverseWords(vector<char>& s) { string sentence(s.begin(), s.end()); stringstream stream(sentence); vector<string> parts; string currentPart; // Extract every word from the complete sentence. while (stream >> currentPart) { parts.push_back(currentPart); } int writeIndex = 0; // Read the stored words from right to left. for (int i = static_cast<int>(parts.size()) - 1; i >= 0; i--) { // Copy every character of the current word. for (int j = 0; j < parts[i].size(); j++) { s[writeIndex] = parts[i][j]; writeIndex++; } // Add a space when another word remains. if (i > 0) { s[writeIndex] = ' '; writeIndex++; } } }};// Driver Code startsint main() { vector<char> s = { 'c', 'o', 'd', 'i', 'n', 'g', ' ', 'i', 's', ' ', 'f', 'u', 'n' }; Solution solution; // Call the function to reverse the order of words. solution.reverseWords(s); // Print the modified character array. for (char ch : s) { cout << ch; } cout << "\n"; return 0;}Complexity Analysis
• Time Complexity: O(N), where N is the total number of characters in the array. Creating the temporary string, extracting the words, and copying the reversed words back each take linear time.
• Space Complexity: O(N), as the temporary string and vector of words require additional memory proportional to the input size.
Optimal Approach
The idea is to reverse each word individually first, followed by reversing the entire character array. Reversing each word changes the order of its characters but keeps the words in their original positions. For example, "coding is fun" becomes "gnidoc si nuf" after reversing each word separately.
Next, reversing the complete character array changes the positions of the words and restores the original character order within each word. The final result becomes "fun is coding". Both operations are performed directly on the original array, so no additional space is needed.
Algorithm
Traverse the character array and identify the beginning and end of each word using spaces as separators.
Reverse each word by maintaining two pointers: one at the beginning and the other at the end of the word.
Swap the characters at both pointers, move the left pointer forward and the right pointer backward, and continue until both pointers meet or cross each other.
Repeat the same process for every word in the array, reversing each word individually.
Once all words are reversed, apply the same two-pointer swapping technique to the entire character array, starting from the first and last positions.
The final array contains the words in reverse order, with the characters of each word restored to their original order.
Dry Run
Reverse Words in a String II - Optimal
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Reverses the characters between two given positions. void reverseRange(vector<char>& s, int left, int right) { // Swap characters until both pointers meet. while (left < right) { swap(s[left], s[right]); left++; right--; } } // Reverses the order of words without using extra space. void reverseWords(vector<char>& s) { int start = 0; int n = s.size(); // Scan the array to find every complete word. for (int end = 0; end <= n; end++) { /* Reverse a word after finding a space or reaching the end of the array. */ if (end == n || s[end] == ' ') { reverseRange(s, start, end - 1); start = end + 1; } } // Reverse the complete array to change the word order. reverseRange(s, 0, n - 1); }};// Driver Code startsint main() { vector<char> s = { 'c', 'o', 'd', 'i', 'n', 'g', ' ', 'i', 's', ' ', 'f', 'u', 'n' }; Solution solution; // Call the function to reverse the order of words. solution.reverseWords(s); // Print the modified character array. for (char ch : s) { cout << ch; } cout << "\n"; return 0;}Complexity Analysis
• Time Complexity: O(N), where N is the total number of characters in the array. Reversing each word and then reversing the complete array both require linear time.
• Space Complexity: O(1), as the operations are performed directly on the original character array using only a few variables for tracking indices and swapping characters. No extra data structure is used.
Interview follow-up Questions
No visible change occurs because only one word is present. The reversal operations may still run, but the final character order remains the same. For example, ["h","e","l","l","o"] still represents "hello" after completion.
Be the first to add a comment.