151. Reverse Words in a String

📝 Problem Details

• Title: 151. Reverse Words in a String
• Link: https://leetcode.com/problems/reverse-words-in-a-string/
• Difficulty: Medium
• Tags/Categories: Strings

input string s, reverse the order of the words word ⇒ a sequence of non-space characters return a string of the words in reverse order concatenated by a single space

💭What Were My Initial Thoughts?

- O(n) additional space solution:
	- Iterate from back to front, skipping trailing spaces.
	- Capture words as you go, add them to a vector or string.
	- Join them later with a single space.

- O(1) solution (in-place):
	- Reverse the entire string.
	- Reverse each word in-place as you find them.
	- Remove leading, trailing, and multiple intermediate spaces.

💡 Explanation of Solution

We reverse the string in place to make the words come in reverse order.
However, the words themselves are also reversed, so we reverse each word again individually.

To handle spaces:
- First remove any leading, trailing, or multiple intermediate spaces.
- Then do the reverse of the entire string.
- Then iterate and reverse each word individually.

⌛ Complexity Analysis

Time Complexity: O(n)
— where n is the length of the string. Each character is visited a constant number of times.

Space Complexity:
- O(1) if done in-place.
- O(n) if using extra string or vector to store intermediate results.

💻 Implementation of Solution

class Solution {
public:
    void reverse(string& s, int start, int end) {
        while (start < end) {
            swap(s[start++], s[end--]);
        }
    }
 
    void removeExtraSpaces(string& s) {
        int n = s.size();
        int i = 0, j = 0;
        
        while (j < n && s[j] == ' ') ++j; // skip leading spaces
        
        while (j < n) {
            if (s[j] != ' ') {
                s[i++] = s[j++];
            } else {
                s[i++] = ' ';
                while (j < n && s[j] == ' ') ++j; // skip multiple spaces
            }
        }
        
        // remove trailing space if it exists
        if (i > 0 && s[i-1] == ' ') --i;
        s.resize(i);
    }
 
    string reverseWords(string s) {
        removeExtraSpaces(s);               // Step 1: Clean up spaces
        reverse(s, 0, s.size() - 1);        // Step 2: Reverse the whole string
 
        int start = 0;
        for (int end = 0; end <= s.size(); ++end) {
            if (end == s.size() || s[end] == ' ') {
                reverse(s, start, end - 1); // Step 3: Reverse each word
                start = end + 1;
            }
        }
 
        return s;
    }
};