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:
- Cree una array de caracteres temporal, digamos temp[].
- Copie los caracteres alfabéticos de la array dada a temp[].
- Reverse temp[] utilizando el algoritmo de inversión de string estándar .
- 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++
//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
// 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
# 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
Producción
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++
// 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
// 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
// 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
Python3
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#
// 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
Javascript
<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>
Producción
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).
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA