Dada una string str que consta de caracteres y números y un número entero k , la tarea es descifrar la string y devolver el k -ésimo carácter en la string descifrada.
Para descifrar la string, recorra la string carácter por carácter y, si el carácter actual es un alfabeto, añádalo a la string resultante; de lo contrario, si es un dígito numérico, analice el número y repita la string resultante esta cantidad de veces analizada y continuar con la string original. Por ejemplo, str = «ab2c3» se descifrará como «ababcababcababc».
Ejemplos:
Entrada: str = “ab2c3”, k = 5
Salida: c La
string descifrada será “ababcababcababc” y ‘c’ es el quinto carácter.
Entrada: str = “x2y3”, k = 3
Salida: y
Acercarse:
- Inicialice el índice inicial i = 0 y total_len = 0 .
- Haga un bucle mientras i sea menor que la longitud de la string de entrada y verifique si el carácter actual es un alfabeto o no. En caso afirmativo, incremente total_len en 1 y verifique si la longitud total es menor o igual a k , en caso afirmativo, devuelva la string; de lo contrario, incremente i .
- Inicialice n = 0 nuevamente en bucle mientras i es menor que la longitud de la string de entrada e i no es un alfabeto y analice el número e incremente i y encuentre next_total_len = total_len * n.
- Si k < total_len entonces obtenga la posición del carácter inicializando pos = k % total_len .
- Si no se encuentra la posición, actualice position = total_len y finalmente devuelva el carácter en la k -ésima posición. Si no se encuentra, devuelve -1 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <cstdlib>
#include <iostream>
using namespace std;
// Function to print kth character of
// String s after decrypting it
char findKthChar(string s, int k)
{
// Get the length of string
int len = s.length();
// Initialise pointer to character
// of input string to zero
int i = 0;
// Total length of resultant string
int total_len = 0;
// Traverse the string from starting
// and check if each character is
// alphabet then increment total_len
while (i < len) {
if (isalpha(s[i])) {
total_len++;
// If total_leg equal to k then
// return string else increment i
if (total_len == k)
return s[i];
i++;
}
else {
// Parse the number
int n = 0;
while (i < len && !isalpha(s[i])) {
n = n * 10 + (s[i] - '0');
i++;
}
// Update next_total_len
int next_total_len = total_len * n;
// Get the position of kth character
if (k <= next_total_len) {
int pos = k % total_len;
// Position not found then update
// position with total_len
if (!pos) {
pos = total_len;
}
// Recursively find the kth position
return findKthChar(s, pos);
}
else {
// Else update total_len
// by next_total_len
total_len = next_total_len;
}
}
}
// Return -1 if character not found
return -1;
}
// Driver code
int main()
{
string s = "ab2c3";
int k = 5;
cout << findKthChar(s, k);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GfG
{
// Function to print kth character of
// String s after decrypting it
static Character findKthChar(String s, int k)
{
// Get the length of string
int len = s.length();
// Initialise pointer to character
// of input string to zero
int i = 0;
// Total length of resultant string
int total_len = 0;
// Traverse the string from starting
// and check if each character is
// alphabet then increment total_len
while (i < len)
{
if (Character.isLetter(s.charAt(i)))
{
total_len++;
// If total_leg equal to k then
// return string else increment i
if (total_len == k)
return s.charAt(i);
i++;
}
else
{
// Parse the number
int n = 0;
while (i < len && !Character.isLetter(s.charAt(i)))
{
n = n * 10 + (s.charAt(i) - '0');
i++;
}
// Update next_total_len
int next_total_len = total_len * n;
// Get the position of kth character
if (k <= next_total_len)
{
int pos = k % total_len;
// Position not found then update
// position with total_len
if (pos == 0)
{
pos = total_len;
}
// Recursively find the kth position
return findKthChar(s, pos);
}
else
{
// Else update total_len
// by next_total_len
total_len = next_total_len;
}
}
}
// Return -1 if character not found
return ' ';
}
// Driver code
public static void main(String[] args)
{
String s = "ab2c3";
int k = 5;
System.out.println(findKthChar(s, k));
}
}
// This code is contributed by Prerna Saini.
Python3
# Python 3 implementation of the approach
# Function to print kth character of
# String s after decrypting it
def findKthChar(s, k):
# Get the length of string
len1 = len(s)
# Initialise pointer to character
# of input string to zero
i = 0
# Total length of resultant string
total_len = 0
# Traverse the string from starting
# and check if each character is
# alphabet then increment total_len
while (i < len1):
if (s[i].isalpha()):
total_len += 1
# If total_leg equal to k then
# return string else increment i
if (total_len == k):
return s[i]
i += 1
else:
# Parse the number
n = 0
while (i < len1 and s[i].isalpha() == False):
n = n * 10 + (ord(s[i]) - ord('0'))
i += 1
# Update next_total_len
next_total_len = total_len * n
# Get the position of kth character
if (k <= next_total_len):
pos = k % total_len
# Position not found then update
# position with total_len
if (pos == 0):
pos = total_len
# Recursively find the kth position
return findKthChar(s, pos)
else:
# Else update total_len
# by next_total_len
total_len = next_total_len
# Return -1 if character not found
return -1
# Driver code
if __name__ == '__main__':
s = "ab2c3"
k = 5
print(findKthChar(s, k))
# This code is contributed by
# Surendra_Gangwar
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to print kth character of
// String s after decrypting it
static char findKthChar(String s, int k)
{
// Get the length of string
int len = s.Length;
// Initialise pointer to character
// of input string to zero
int i = 0;
// Total length of resultant string
int total_len = 0;
// Traverse the string from starting
// and check if each character is
// alphabet then increment total_len
while (i < len)
{
if (char.IsLetter(s[i]))
{
total_len++;
// If total_leg equal to k then
// return string else increment i
if (total_len == k)
return s[i];
i++;
}
else
{
// Parse the number
int n = 0;
while (i < len && !char.IsLetter(s[i]))
{
n = n * 10 + (s[i] - '0');
i++;
}
// Update next_total_len
int next_total_len = total_len * n;
// Get the position of kth character
if (k <= next_total_len)
{
int pos = k % total_len;
// Position not found then update
// position with total_len
if (pos == 0)
{
pos = total_len;
}
// Recursively find the kth position
return findKthChar(s, pos);
}
else
{
// Else update total_len
// by next_total_len
total_len = next_total_len;
}
}
}
// Return -1 if character not found
return ' ';
}
// Driver code
public static void Main(String[] args)
{
String s = "ab2c3";
int k = 5;
Console.WriteLine(findKthChar(s, k));
}
}
// This code is contributed by PrinciRaj1992
Producción:
c
Complejidad de tiempo: O(N)
Espacio Auxiliar: O(1)