Invierta una string sin afectar los caracteres especiales

Dada una string que contiene un carácter especial junto con letras (‘a’ a ‘z’ y ‘A’ a ‘Z’), invierta la string de manera que los caracteres especiales no se vean afectados.

Ejemplos: 

Input:   str = "a,b$c"
Output:  str = "c,b$a"
Note that $ and , are not moved anywhere.  
Only subsequence "abc" is reversed

Input:   str = "Ab,c,de!$"
Output:  str = "ed,c,bA!$"

Solución simple: 

1. Cree una array de caracteres temporal, digamos temp[]. 
2. Copie los caracteres alfabéticos de la array dada a temp[]. 
3. Reverse temp[] utilizando el algoritmo de inversión de string estándar . 
4. Ahora atraviesa la string de entrada y la temperatura en un solo ciclo. Siempre que haya un carácter alfabético que sea una string de entrada, reemplácelo con el carácter actual de temp[].

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

//C++ program to reverse string without
//affecting it's special character
 
#include<bits/stdc++.h>
using namespace std;
void reverse(string s){
    //creating character array of size
    // equal to length of string
    char temp[s.length()];
    int x=0;
    for (int i = 0; i < s.length(); i++)
    {
        if(s[i]>='a' && s[i]<='z' || s[i]>='A' && s[i]<='Z'){
            //storing elements in array
          temp[x]=s[i];
          x++;
        }
    }
    //reversing the character array
    reverse(temp,temp+x);
 
     
    x=0;
    for (int i = 0; i < s.length(); i++)
    {
        if(s[i]>='a' && s[i]<='z' || s[i]>='A' && s[i]<='Z'){
            //updating the origional string
            s[i]=temp[x];
            x++;
        }
    }
    cout<<"reversed string is: "<<s;
     
}
//driver code
int main() {
string s="Ab,c,de!$";
//function call
reverse(s);
return 0;
}
 
//this code is contributed by Machhaliya Muhammad

// Java code to illustrate how to reverse an array without
// affecting special characters.
import java.util.*;
 
class GFG {
    public static void rev(char s[], int l, int r)
    {
        for (int i = l; i < r / 2; i++) {
            char temp = s[i];
            s[i] = s[r - 1 - i];
            s[r - 1 - i] = temp;
        }
    }
    public static void reverse(char s[])
    {
        // creating character array of size
        // equal to length of string
        char[] temp = new char[s.length];
        int x = 0;
        for (int i = 0; i < s.length; i++) {
            if (s[i] >= 'a' && s[i] <= 'z'
                || s[i] >= 'A' && s[i] <= 'Z') {
                // storing elements in array
                temp[x] = s[i];
                x++;
            }
        }
 
        // reversing the character array
        rev(temp, 0, x);
 
        x = 0;
        for (int i = 0; i < s.length; i++) {
            if (s[i] >= 'a' && s[i] <= 'z'
                || s[i] >= 'A' && s[i] <= 'Z') {
                // updating the origional string
                s[i] = temp[x];
                x++;
            }
        }
 
        String revStr = new String(s);
        System.out.println("reversed string is: " + revStr);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        String str = "Ab,c,de!$";
        char[] charArray = str.toCharArray();
        reverse(charArray);
    }
}
 
// This code is contributed by Aarti_Rathi

# Python3 program to reverse string without
# affecting it's special character
def rev(s, l, r) :
    while l<r :
        temp = s[l]
        s[l] = s[r]
        s[r] = temp
        l += 1
        r -= 1
     
# creating character array of size
# equal to length of string
def reverse(s):
     
    temp = ['']*len(s)
    x = 0
     
    for i in range(len(s)) :
        if s[i] >= 'a' and s[i] <= 'z' or s[i] >= 'A' and s[i] <= 'Z' :
            # storing elements in array
            temp[x] = s[i]
            x += 1
     
    # reversing the character array       
    rev(temp, 0, x)
     
    lst = list(s)
    x = 0
     
    for i in range(len(s)) :
        if s[i] >= 'a' and s[i] <= 'z' or s[i] >= 'A' and s[i] <= 'Z' :
            # updating the origional string
            lst[i] = temp[x]
            x += 1
     
    revStr = ""
    for i in range(len(s)) :
        revStr += lst[i]
         
    print("reverse string is :",revStr);
     
# Driver Code
if __name__ == "__main__" :
     
    s="Ab,c,de!$"
     
    reverse(s)
     
# This code is contributed by aditya942003patil

reversed string is: ed,c,bA!$

Complejidad temporal: O(N) donde N es la longitud de la string.
Complejidad del espacio auxiliar: O(N) donde N es la longitud de la string.

Solución eficiente: 

La complejidad temporal de la solución anterior es O(n), pero requiere espacio adicional y realiza dos recorridos de una string de entrada. 
Podemos invertir con un recorrido y sin espacio extra. A continuación se muestra el algoritmo. 

1) Let input string be 'str[]' and length of string be 'n'
2) l = 0, r = n-1
3) While l is smaller than r, do following
    a) If str[l] is not an alphabetic character, do l++
    b) Else If str[r] is not an alphabetic character, do r--
    c) Else swap str[l] and str[r]

A continuación se muestran implementaciones del algoritmo anterior.

// C++ program to reverse a string  with special characters
#include <bits/stdc++.h>
using namespace std;
 
// Returns true if x is an alphabetic character, false
// otherwise
bool isAlphabet(char x)
{
    return ((x >= 'A' && x <= 'Z') || (x >= 'a' && x <= 'z'));
}
 
void reverse(char str[])
{
    // Initialize left and right pointers
    int r = strlen(str) - 1, l = 0;
 
    // Traverse string from both ends until 'l' and 'r'
    while (l < r) {
        // Ignore special characters
        if (!isAlphabet(str[l]))
            l++;
        else if (!isAlphabet(str[r]))
            r--;
 
        else // Both str[l] and str[r] are not special
        {
            swap(str[l], str[r]);
            l++;
            r--;
        }
    }
}
 
// Driver code
int main()
{
    char str[] = "a!!!b.c.d,e'f,ghi";
    cout << "Input string: " << str << endl;
    reverse(str);
    cout << "Output string: " << str << endl;
    return 0;
}
 
// This code is contributed by Sania Kumari Gupta

// C program to reverse a string with special characters
#include <stdbool.h>
#include <stdio.h>
#include <string.h>
// Returns true if x is an alphabetic character, false
// otherwise
bool isAlphabet(char x)
{
    return ((x >= 'A' && x <= 'Z') || (x >= 'a' && x <= 'z'));
}
 
void reverse(char str[])
{
    // Initialize left and right pointers
    int r = strlen(str) - 1, l = 0;
 
    // Traverse string from both ends until 'l' and 'r'
    while (l < r) {
        // Ignore special characters
        if (!isAlphabet(str[l]))
            l++;
        else if (!isAlphabet(str[r]))
            r--;
        // Both str[l] and str[r] are not special
        else {
            char temp = str[l];
            str[l] = str[r];
            str[r] = temp;
            // swap(str[l], str[r]);
            l++;
            r--;
        }
    }
}
 
// Driver code
int main()
{
    char str[] = "a!!!b.c.d,e'f,ghi";
    printf("Input string: %s\n", str);
    reverse(str);
    printf("Output string: %s\n", str);
    return 0;
}
 
// This code is contributed by Sania Kumari Gupta

// Java code to illustrate how to reverse an array without
// affecting special characters.
class GFG {
    public static void reverse(char str[])
    {
        // Initialize left and right pointers
        int r = str.length - 1, l = 0;
 
        // Traverse string from both ends until 'l' and 'r'
        while (l < r) {
            // Ignore special characters
            if (!Character.isAlphabetic(str[l]))
                l++;
            else if (!Character.isAlphabetic(str[r]))
                r--;
 
            // Both str[l] and str[r] are not spacial
            else {
                char tmp = str[l];
                str[l] = str[r];
                str[r] = tmp;
                l++;
                r--;
            }
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        String str = "a!!!b.c.d,e'f,ghi";
        char[] charArray = str.toCharArray();
 
        System.out.println("Input string: " + str);
        reverse(charArray);
        String revStr = new String(charArray);
 
        System.out.println("Output string: " + revStr);
    }
}
 
// This code is contributed by Sania Kumari Gupta

def reverseString(text):
    index = -1
 
    # Loop from last index until half of the index    
    for i in range(len(text)-1, int(len(text)/2), -1):
 
        # match character is alphabet or not        
        if text[i].isalpha():
            temp = text[i]
            while True:
                index += 1
                if text[index].isalpha():
                    text[i] = text[index]
                    text[index] = temp
                    break
    return text
     
# Driver code
string = "a!!!b.c.d,e'f,ghi"
print ("Input string: ", string)
string = reverseSting(list(string))
print ("Output string: ", "".join(string))
  
# This code is contributed by shiva9610

// C# code to illustrate how to reverse
// an array without affecting special characters.
using System;
public class GFG
{
    public static void reverse(char []str)
    {
        // Initialize left and right pointers
        int r = str.Length - 1, l = 0;
 
        // Traverse string from both ends until
        // 'l' and 'r'
        while (l < r)
        {
            // Ignore special characters
            if (!char.IsLetter(str[l]))
                l++;
            else if(!char.IsLetter(str[r]))
                r--;
 
            // Both str[l] and str[r] are not spacial
            else
            {
                char tmp = str[l];
                str[l] = str[r];
                str[r] = tmp;
                l++;
                r--;
            }
        }
    }
 
    // Driver Code
    public static void Main()
    {
        String str = "a!!!b.c.d,e'f,ghi";
        char[] charArray = str.ToCharArray();
 
        Console.WriteLine("Input string: " + str);
                            reverse(charArray);
        String revStr = new String(charArray);
 
        Console.WriteLine("Output string: " + revStr);
    }
}
 
// This code is contributed by PrinciRaj1992

<script>
 
// JavaScript program to reverse a string
// with special characters
 
// Returns true if x is an alphabetic
// character, false otherwise
function isAlphabet( x)
{
    return ( (x >= 'A' && x <= 'Z') ||
             (x >= 'a' && x <= 'z') );
}
function swap(str,a,b)
{
    var c="";
    for(var i=0;i<str.length;i++)
    {
        if(i==a)
         c= c+ str[b];
         else
            if(i==b)
                c=c+str[a];
               else
               c=c+str[i];
             
    }
    return c;
   }
     
 
function reverse( str)
{
    // Initialize left and right pointers
    var r = str.length - 1, l = 0;
 
    // Traverse string from both ends until
    // 'l' and 'r'
    while (l < r)
    {
        // Ignore special characters
        if (!isAlphabet(str[l]))
            l++;
        else if(!isAlphabet(str[r]))
            r--;
 
        else // Both str[l] and str[r] are not spacial
        {
            str=swap(str,l, r);
            l++;
            r--;
        }
    }
    document.write("Output string: "+ str +"<br>");
}
 
 
    var str= "a!!!b.c.d,e'f,ghi";
    document.write( "Input string: " + str +"<br>");
    reverse(str);
    
  
</script>

Input string: a!!!b.c.d,e'f,ghi
Output string: i!!!h.g.f,e'd,cba

Complejidad temporal: O(N) donde N es la longitud de la string.
Complejidad del espacio auxiliar: O(1).