151. Reverse Words in a String: Leetcode Step-by-Step Approach

Reverse Words in a String - LeetCode

Photo by Christopher Gower on Unsplash

PROBLEM STATEMENT:

Given an input string s, reverse the order of the words.

A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.

Return a string of the words in reverse order concatenated by a single space.

Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

APPROACH 1: TOKENISATION

Step 1: Tokenization and Stack Initialization
- The input path is tokenized using a `stringstream` and the delimiter `’/’`.
- A stack (`st`) is initialized to store valid directory names while processing the input path.

Step 2: Token Processing Loop
- A loop iterates through each token obtained from the tokenization process.
- If the token is an empty string (`"”`) or represents the current directory (`”.”`), it is skipped as it doesn’t contribute to the path.
- If the token is `”..”`, it represents a parent directory reference. In this case, if the stack is not empty, the top directory is popped from the stack to move up one level in the directory structure.
- Otherwise, if the token is a valid directory name, it is pushed onto the stack to be included in the simplified path.

Step 3: Constructing the Simplified Path
- After processing all tokens, a string `result` is initialized to store the simplified path.
- A loop iterates through the stack of valid directories (`st`).
- For each directory, it adds the directory name to the beginning of the `result` string, preceded by a slash (“/”). The directory is then popped from the stack.
- This loop effectively constructs the simplified path in reverse order.

Step 4: Handling Empty Result
- If the `result` string is still empty after the loop, it means no valid directories were present in the input path.
- In this case, the minimum root directory (“/”) is added to the `result` to ensure there is at least a root in the simplified path.

Step 5: Return Result
- The `result` string, which represents the simplified path, is returned as the final output.

#include <sstream>
#include <string>
#include<iostream>

using namespace std;

class Solution {
public:
    string reverseWords(string s) {
        stringstream ss(s);
        string token = "";

        string result = "";
        while (ss >> token) {
            result = token + " " + result;
        }

        return result.substr(0, result.length() - 1);
    }
};

int main() {
    Solution solution;
    string input = "the sky is blue";
    string reversed = solution.reverseWords(input);
    cout << "Original: " << input << endl;
    cout << "Reversed: " << reversed << endl;
    return 0;
}

TIME AND SPACE COMPLEXITY: O(N)

APPROACH: TWO POINTER

Step 1: Reverse the Entire String
- The input string `s` is reversed using the `reverse` function, effectively reversing the order of all characters in the string.

Step 2: Initialize Pointers and Length
- Initialize three integer variables: `i` (a current position pointer), `l` (start of a word pointer), and `r` (end of a word pointer).
- Get the length of the string `s` and store it in the variable `n`.

Step 3: Tokenize and Reverse Words
- Start a loop that iterates through the string `s` using the current position pointer `i`.
- Inside the loop, there’s another loop that runs while `i` is within bounds and the character at position `i` is not a space (“ ”).
- In this inner loop, the characters of the current word are copied from the position `i` to position `r` in the string. The `r` pointer is incremented along with `i` to keep track of the word’s end.

Step 4: Reverse and Store Words
- After a word has been copied, check if `l` is less than `r`, indicating that a word was indeed copied.
- If a word was copied, reverse the characters of the word from position `l` to position `r-1` using the `reverse` function.
- Place a space (‘ ‘) at position `r` in the string to separate the reversed words.
- Increment `r` to point to the next position after the added space.
- Set `l` equal to `r`, effectively moving the `l` pointer to the start of the next word.

Step 5: Iterate and Process Characters
- Increment the current position pointer `i` to move to the next character.
- The loop continues until all characters in the string `s` have been processed.

Step 6: Trim and Return the Result
- After processing all characters, the string `s` contains the reversed words with spaces between them.
- Use the `substr` function to extract a substring of the string `s` from the beginning up to the position `r-1`. This removes any trailing space.
- Return the result string, which represents the reversed words with reversed order.
This approach reverses the entire input string and then processes it character by character to reverse each word while maintaining their order. The result is a string with words reversed and the overall order of words preserved.

#include <iostream>
#include <algorithm>
using namespace std;

class Solution {
public:
    string reverseWords(string s) {
        reverse(s.begin(), s.end());
        
        int i = 0;
        int l = 0, r = 0;
        int n = s.length();
        
        while (i < n) {
            while (i < n && s[i] != ' ') {
                s[r++] = s[i++];
            }
            
            if (l < r) {
                reverse(s.begin() + l, s.begin() + r);
                s[r] = ' ';
                r++;
                l = r;
            }
            
            i++;
        }
        
        s = s.substr(0, r - 1);
        
        return s;
    }
};

int main() {
    Solution solution;
    string input = "the sky is blue";
    string reversed = solution.reverseWords(input);
    
    cout << "Original: " << input << endl;
    cout << "Reversed: " << reversed << endl;
    
    return 0;
}

SPACE AND TIME COMPLEXITY: O(N)

RESOURCE: