Dada una string S y una array de índices A[] , la tarea es invertir las substrings de la string dada de acuerdo con la array de índices dada.
Nota: A[i] ≤ longitud(S), para todo i.
Ejemplos:
Entrada: S = “abcdef”, A[] = {2, 5}
Salida: baedcf
Explicación:
Entrada: S = “abcdefghij”, A[] = {2, 5}
Salida: baedcjihgf
Enfoque: La idea es utilizar el concepto de invertir las substrings de la string dada.
- Ordenar la array de índices.
- Extraiga la substring formada para cada índice en la array dada de la siguiente manera:
- Para el primer índice en la array A, la substring formada será del índice 0 a A[0] (exclusivo) de la string dada, es decir, [0, A[0])
- Para todos los demás índices en la array A (excepto el último), la substring formada será del índice A[i] a A[i+1] (exclusivo) de la string dada, es decir, [A[i], A[i +1])
- Para el último índice de la array A, la substring formada será desde el índice A[i] hasta L (inclusive), donde L es la longitud de la string, es decir, [A[i], L]
- Invierta cada substring encontrada en la string dada
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ implementation to reverse
// the substrings of the given String
// according to the given Array of indices
#include <bits/stdc++.h>
using namespace std;
// Function to reverse a string
void reverseStr(string& str,
int l, int h)
{
int n = h - l;
// Swap character starting
// from two corners
for (int i = 0; i < n / 2; i++) {
swap(str[i + l], str[n - i - 1 + l]);
}
}
// Function to reverse the string
// with the given array of indices
void reverseString(string& s, int A[], int n)
{
// Reverse the string from 0 to A[0]
reverseStr(s, 0, A[0]);
// Reverse the string for A[i] to A[i+1]
for (int i = 1; i < n; i++)
reverseStr(s, A[i - 1], A[i]);
// Reverse String for A[n-1] to length
reverseStr(s, A[n - 1], s.length());
}
// Driver Code
int main()
{
string s = "abcdefgh";
int A[] = { 2, 4, 6 };
int n = sizeof(A) / sizeof(A[0]);
reverseString(s, A, n);
cout << s;
return 0;
}
Java
// Java implementation to reverse
// the subStrings of the given String
// according to the given Array of indices
class GFG
{
static String s;
// Function to reverse a String
static void reverseStr(int l, int h)
{
int n = h - l;
// Swap character starting
// from two corners
for (int i = 0; i < n / 2; i++)
{
s = swap(i + l, n - i - 1 + l);
}
}
// Function to reverse the String
// with the given array of indices
static void reverseString(int A[], int n)
{
// Reverse the String from 0 to A[0]
reverseStr(0, A[0]);
// Reverse the String for A[i] to A[i+1]
for (int i = 1; i < n; i++)
reverseStr(A[i - 1], A[i]);
// Reverse String for A[n-1] to length
reverseStr(A[n - 1], s.length());
}
static String swap(int i, int j)
{
char ch[] = s.toCharArray();
char temp = ch[i];
ch[i] = ch[j];
ch[j] = temp;
return String.valueOf(ch);
}
// Driver Code
public static void main(String[] args)
{
s = "abcdefgh";
int A[] = { 2, 4, 6 };
int n = A.length;
reverseString(A, n);
System.out.print(s);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation to reverse
# the substrings of the given String
# according to the given Array of indices
# Function to reverse a string
def reverseStr(str, l, h):
n = h - l
# Swap character starting
# from two corners
for i in range(n//2):
str[i + l], str[n - i - 1 + l] = str[n - i - 1 + l], str[i + l]
# Function to reverse the string
# with the given array of indices
def reverseString(s, A, n):
# Reverse the from 0 to A[0]
reverseStr(s, 0, A[0])
# Reverse the for A[i] to A[i+1]
for i in range(1, n):
reverseStr(s, A[i - 1], A[i])
# Reverse String for A[n-1] to length
reverseStr(s, A[n - 1], len(s))
# Driver Code
s = "abcdefgh"
s = [i for i in s]
A = [2, 4, 6]
n = len(A)
reverseString(s, A, n)
print("".join(s))
# This code is contributed by mohit kumar 29
C#
// C# implementation to reverse
// the subStrings of the given String
// according to the given Array of indices
using System;
class GFG
{
static String s;
// Function to reverse a String
static void reverseStr(int l, int h)
{
int n = h - l;
// Swap character starting
// from two corners
for (int i = 0; i < n / 2; i++)
{
s = swap(i + l, n - i - 1 + l);
}
}
// Function to reverse the String
// with the given array of indices
static void reverseString(int []A, int n)
{
// Reverse the String from 0 to A[0]
reverseStr(0, A[0]);
// Reverse the String for A[i] to A[i+1]
for (int i = 1; i < n; i++)
reverseStr(A[i - 1], A[i]);
// Reverse String for A[n-1] to length
reverseStr(A[n - 1], s.Length);
}
static String swap(int i, int j)
{
char []ch = s.ToCharArray();
char temp = ch[i];
ch[i] = ch[j];
ch[j] = temp;
return String.Join("",ch);
}
// Driver Code
public static void Main(String[] args)
{
s = "abcdefgh";
int []A = { 2, 4, 6 };
int n = A.Length;
reverseString(A, n);
Console.Write(s);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript implementation to reverse
// the substrings of the given String
// according to the given Array of indices
// Function to reverse a string
function reverseStr(str, l, h)
{
var n = h - l;
// Swap character starting
// from two corners
for (var i = 0; i < n / 2; i++) {
[str[i + l], str[n - i - 1 + l]] =
[str[n - i - 1 + l], str[i + l]];
}
return str;
}
// Function to reverse the string
// with the given array of indices
function reverseString(s, A, n)
{
// Reverse the string from 0 to A[0]
s = reverseStr(s, 0, A[0]);
// Reverse the string for A[i] to A[i+1]
for (var i = 1; i < n; i++)
s = reverseStr(s, A[i - 1], A[i]);
// Reverse String for A[n-1] to length
s = reverseStr(s, A[n - 1], s.length);
return s;
}
// Driver Code
var s = "abcdefgh";
var A = [2, 4, 6];
var n = A.length;
s = reverseString(s.split(''), A, n);
document.write( s.join(''));
</script>
Producción:
badcfehg
Publicación traducida automáticamente
Artículo escrito por Sanjit_Prasad y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA