Reverse individual words with O(1) extra space
Given a string str, the task is to reverse all the individual words.
Examples:
Input: str = “Hello World”
Output: olleH dlroWInput: str = “Beginner for Beginner”
Output: skeeG rof skeeG
Approach: A solution to the above problem has been discussed in this post. It has a time complexity of O(n) and uses O(n) extra space. In this post, we will discuss a solution which uses O(1) extra space.
- Traverse through the string until we encounter a space.
- After encountering the space, we use two variables ‘start’ and ‘end’ pointing to the first and last character of the word and we reverse that particular word.
- Repeat the above steps until the last word.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the string after // reversing the individual words string reverseWords(string str) { // Pointer to the first character // of the first word int start = 0; for ( int i = 0; i <= str.size(); i++) { // If the current word has ended if (str[i] == ' ' || i == str.size()) { // Pointer to the last character // of the current word int end = i - 1; // Reverse the current word while (start < end) { swap(str[start], str[end]); start++; end--; } // Pointer to the first character // of the next word start = i + 1; } } return str; } // Driver code int main() { string str = "Beginner for Beginner" ; cout << reverseWords(str); return 0; } |
Java
// Java implementation of the approach class GFG { static String swap(String str, int i, int j) { StringBuilder sb = new StringBuilder(str); sb.setCharAt(i, str.charAt(j)); sb.setCharAt(j, str.charAt(i)); return sb.toString(); } // Function to return the string after // reversing the individual words static String reverseWords(String str) { // Pointer to the first character // of the first word int start = 0 ; for ( int i = 0 ; i < str.length(); i++) { // If the current word has ended if (str.charAt(i) == ' ' || i == str.length()- 1 ) { // Pointer to the last character // of the current word int end; if (i == str.length()- 1 ) end = i ; else end = i - 1 ; // Reverse the current word while (start < end) { str = swap(str,start,end) ; start++; end--; } // Pointer to the first character // of the next word start = i + 1 ; } } return str ; } // Driver code public static void main(String args[]) { String str = "Beginner for Beginner" ; System.out.println(reverseWords(str)); } } // This code is contributed by AnkitRai01 |
Python3
# Python3 implementation of the approach # Function to return the after # reversing the individual words def reverseWords( Str ): # Pointer to the first character # of the first word start = 0 for i in range ( len ( Str )): # If the current word has ended if ( Str [i] = = ' ' or i = = len ( Str ) - 1 ): # Pointer to the last character # of the current word end = i - 1 if (i = = len ( Str ) - 1 ): end = i # Reverse the current word while (start < end): Str [start], Str [end] = Str [end], Str [start] start + = 1 end - = 1 # Pointer to the first character # of the next word start = i + 1 return "".join( Str ) # Driver code Str = "Beginner for Beginner" Str = [i for i in Str ] print (reverseWords( Str )) # This code is contributed by mohit kumar 29 |
C#
// C# implementation of the approach using System; class GFG { // Function to return the string after // reversing the individual words // Function to return the string after // reversing the individual words static String reverseWords(String str) { // Pointer to the first character // of the first word int start = 0; for ( int i = 0; i < str.Length; i++) { // If the current word has ended if (str[i] == ' ' || i == str.Length-1 ) { // Pointer to the last character // of the current word int end; if (i == str.Length-1) end = i ; else end = i - 1 ; // Reverse the current word while (start < end) { str = swap(str,start,end) ; start++; end--; } // Pointer to the first character // of the next word start = i + 1; } } return str ; } static String swap(String str, int i, int j) { char []ch = str.ToCharArray(); char temp = ch[i]; ch[i] = ch[j]; ch[j] = temp; return String.Join( "" ,ch); } // Driver code public static void Main(String []args) { String str = "Beginner for Beginner" ; Console.WriteLine(reverseWords(str)); } } /* This code is contributed by PrinciRaj1992 */ |
Javascript
<script> // Javascript implementation of the approach function swap(str, i, j) { let sb = str.split( "" ); sb[i] = str[j]; sb[j] = str[i]; return sb.join( "" ); } // Function to return the string after // reversing the individual words function reverseWords(str) { // Pointer to the first character // of the first word let start = 0; for (let i = 0; i < str.length; i++) { // If the current word has ended if (str[i] == ' ' || i == str.length-1 ) { // Pointer to the last character // of the current word let end; if (i == str.length-1) end = i ; else end = i - 1 ; // Reverse the current word while (start < end) { str = swap(str, start, end); start++; end--; } // Pointer to the first character // of the next word start = i + 1; } } return str; } // Driver code let str = "Beginner for Beginner" ; document.write(reverseWords(str)); // This code is contributed by unknown2108 </script> |
Output:
skeeG rof skeeG
Time Complexity: O(n)
Auxiliary Space: O(1)