Invertir palabras individuales con O(1) espacio adicional

Dada una string str , la tarea es invertir todas las palabras individuales.

Ejemplos: 

Entrada: str = “Hola mundo” 
Salida: olleH dlroW

Entrada: str = «Geeks para Geeks» 
Salida: skeeG rof skeeG 
 

Enfoque: En esta publicación se ha discutido una solución al problema anterior . Tiene una complejidad temporal de O(n) y usa O(n) espacio adicional. En esta publicación, discutiremos una solución que usa O(1) espacio adicional.  

  • Atraviesa la cuerda hasta que nos encontremos con un espacio.
  • Después de encontrar el espacio, usamos dos variables ‘inicio’ y ‘fin’ que apuntan al primer y último carácter de la palabra e invertimos esa palabra en particular.
  • Repita los pasos anteriores hasta la última palabra.

A continuación se muestra la implementación del enfoque anterior:  

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 = "Geeks for Geeks";
 
    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 = "Geeks for Geeks";
     
        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 = "Geeks for Geeks"
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 = "Geeks for Geeks";
     
        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 = "Geeks for Geeks";
document.write(reverseWords(str));
 
// This code is contributed by unknown2108
 
</script>
Producción: 

skeeG rof skeeG

 

Complejidad temporal: O(n) 
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por Vindusha y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *