Reverse Words

Given a String str, reverse the string without reversing its individual words. Words are separated by dots.

Note: The last character has not been ‘.’. 

Examples :

Input: str = i.like.this.program.very.much
Output: much.very.program.this.like.i
Explanation: After reversing the whole string(not individual words), the input string becomes much.very.program.this.like.i

Input: str = pqr.mno
Output: mno.pqr
Explanation: After reversing the whole string , the input string becomes mno.pqr

Expected Time Complexity: O(|str|)
Expected Auxiliary Space: O(|str|)

Constraints:
1 <= |str| <= 10⁵

Approach 01:

#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>

class Solution {
public:
    // Function to reverse words in a given string.
    std::string reverseWords(std::string inputString) {
        std::vector<std::string> wordList;
        std::string word;
        std::stringstream ss(inputString);

        // Splitting the string by '.' into words
        while (getline(ss, word, '.')) {
            wordList.push_back(word);
        }

        // Reversing the words list
        std::reverse(wordList.begin(), wordList.end());

        // Joining the reversed words list
        std::string reversedString;
        for (size_t i = 0; i < wordList.size(); i++) {
            reversedString += wordList[i];
            if (i != wordList.size() - 1) {
                reversedString += ".";
            }
        }

        return reversedString;
    }
};

class Solution:
    # Function to reverse words in a given string.
    def reverseWords(self, inputString):
        wordList = inputString.split('.')
        reversedWordList = wordList[::-1]
        reversedString = '.'.join(reversedWordList)
        
        if reversedString[-1] == '.':
            return reversedString[:-1]
        return reversedString

Time Complexity

• Splitting the string by `.`:

  To split the input string by `.` into individual words, we are iterating through the entire string. Let \(n\) be the length of the input string. The time complexity of this step is \(O(n)\).

• Reversing the words list:

  The words are stored in a vector, and reversing the vector takes \(O(k)\), where \(k\) is the number of words in the string.

• Joining the words back:

  Concatenating the reversed words to form the final string takes \(O(n)\), since we are iterating through each word and joining them into the final string.

• Overall Time Complexity:

  The overall time complexity is \(O(n)\), where \(n\) is the length of the input string, since splitting, reversing, and joining all operate linearly on the string length.

Space Complexity

• Space for storing words:

  The vector `wordList` stores all the words, which takes \(O(n)\) space, where \(n\) is the length of the input string (in the worst case, each character could be a separate word).

• Space for the result string:

  The result string will also take \(O(n)\) space to store the reversed words.

• Auxiliary space for the stringstream and temporary variables:

  The stringstream and temporary string variables will take \(O(n)\) space in total, but they are temporary and reused.

• Overall Space Complexity:

  The overall space complexity is \(O(n)\), as the vector and result string both depend on the length of the input string.