Reverse Words in a String in Data Structures

Example

Input :

Output :

Example Explanation

The string given to us is "welcome to scaler topics". To reverse the words of this string, we need to think of a logic to reverse the words and also to remove any leading or trailing spaces. This gives us "topics scaler to welcome".

Constraints

• Length of the string s will be between 1 and 104.
• s could contain English letters (upper-case and lower-case), digits, and spaces ' '.
• There is at least one word in s.

Approach 1 : Splitting and Saving the String in a Reverse Manner

One of the easiest ways to reverse words in a string is by splitting the string and then saving it in reverse order. This is the naive approach. We will now look at the code for this method :

Java Implementation

In Java, we have the split method, which helps us split the string. We use it to split the string using the delimiter and reverse and store the line in another variable.

Output :

Python Implementation

In python too, we have the split method, which helps us split the string. We use it to split the string using the delimiter and reverse and store the line in another variable.

Output :

C++ Implementation

Output :

Complexity Analysis

Let's analyze the time and space complexity of this approach :

Time Complexity : $O(n)$ as we use only one for a loop.
Space Complexity : $O(n)$ as we are storing our output that is, the reversed string in a new variable.

Approach 2 : Using the Two-Pointers Approach

Now, here comes the optimal solution for this problem.

We initialize two pointers, one at the start of the string and another at the end. Then, we swap the words from the start and end, to achieve the reversed string.

Algorithm :

1. Turn the string s into an array of strings in which the words of s are stored.
2. Now, initialise the left and right pointers at 0 and $s.length()$ – $1$.
3. Now, we need to swap the elements at the left and right pointers. For that, move the left pointer ahead and the right pointer backward by one position and swap the elements at each position while the left pointer does not exceed the right pointer.
4. Return the final string.

Java Implementation

Output :

Python Implementation

Output :

C++ Implementation

Output :

Complexity Analysis

Let's analyze the time and space complexity of this approach :

Time Complexity : $O(n)$
Space Complexity : $O(1)$