Dada una string codificada (o encriptada) S de longitud N , un entero M. La tarea es descifrar la string cifrada e imprimirla. Las técnicas de cifrado y descifrado se dan como:
Cifrado : la string original se coloca en una array de M filas y N/M columnas, de modo que el primer carácter del texto o string original se coloca en la celda superior izquierda de la manera inferior derecha . Si se llega a la última fila, vuelva a ir a la fila superior y comience desde la siguiente columna.
Por ejemplo: si la string es «geeks», M = 2, entonces la string se cifrará de la siguiente manera
Luego recorra la fila de la array e imprima los caracteres a medida que aparecen.
Por lo tanto, la string anterior se cifrará como = «ges ek»
Descifrado : Atraviese la array en diagonal de la misma manera que se encriptó y encuentre la string real .
Ejemplos :
Entrada: “GSRE_ _ _E_ _K_ _ _EFGS_ _ _KOE” (Aquí ‘_’ significa un espacio), 4
Salida : “GEEKS FOR GEEKS”
Explicación: vea la imagen a continuación para comprender el enfoque.
Aquí el número de columna es 6.
Entonces, el desplazamiento comienza desde la posición (0, 0), luego sube hasta el final de la fila, lo que significa desde (0, 0) –> (1, 1)–>(2, 2)– >(3, 3)–>(4, 4). Luego
vaya a la primera fila y comience desde la siguiente, significa desde (0, 1)–>(1, 2)–>(2, 3)->(3, 4) y continúa hasta llegar al final de la string dada.Entrada: “GEEKSFORGEEKS”, 1
Salida: “GEEKSFORGEEKS”
Explicación: Solo hay una fila. por lo que la string decodificada será igual a la string codificada dada.
Entrada: “abc de”, 2
Salida: “adbec”
Enfoque: Primero, encuentre el número de columnas. Luego, comience a atravesar. Siga los pasos a continuación para resolver el problema:
- Para cada una de las columnas, suba hasta la longitud de la string a partir de la i-ésima fila y, después de cada recorrido, aumente el valor de iteración a column+1 .
- Porque aquí el recorrido se realiza en diagonal, y aquí el siguiente carácter diagonal estará después del número de columna más uno.
Por ejemplo, en la imagen de abajo, la X es un carácter, cuyo siguiente carácter diagonal es XX, y el número de columna donde X está presente es 2, el número de fila del siguiente carácter es solo uno mayor que el anterior.
- En el momento de atravesar, agregue los caracteres en una string vacía. Luego verifique si hay algún espacio al final de la string o no, si es así, simplemente elimínelo.
Por último, imprima esa string, y esta será la string decodificada/string deseada.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the desire string
string decodeString(string encodedText, int rows)
{
// Stores the length of the string
int len = encodedText.size();
// Stores the number of columns
int cols = len / rows;
// Declaring an empty string
string res;
for (int i = 0; i < cols; ++i)
for (int j = i; j < len; j += cols + 1)
// Adding the characters
// into the empty string
res += encodedText[j];
// If their any space at the end,
// delete it
while (res.back() == ' ') {
res.pop_back();
}
return res;
}
// Driver Code
int main()
{
string S = "GSRE E K EFGS KOE";
int row = 4;
cout << decodeString(S, row) << endl;
return 0;
}
Java
// Java program for the above approach
class GFG {
// Function to find the desire string
static String decodeString(String encodedText, int rows) {
// Stores the length of the string
int len = encodedText.length();
// Stores the number of columns
int cols = len / rows;
// Declaring an empty string
String res = "";
for (int i = 0; i < cols; ++i)
{
for (int j = i; j < len; j += cols + 1)
{
// Adding the characters
// into the empty string
res += encodedText.charAt(j);
}
}
// If their any space at the end,
// delete it
while (res.charAt(res.length() - 1) == ' ') {
res = res.substring(0, res.length() - 2);
}
return res;
}
// Driver Code
public static void main(String args[]) {
String S = "GSRE E K EFGS KOE";
int row = 4;
System.out.println(decodeString(S, row));
}
}
// This code is contributed by gfgking
Python3
# Python code for the above approach # Function to find the desire string def decodeString(encodedText, rows): # Stores the length of the string _len = len(encodedText) # Stores the number of columns cols = _len // rows # Declaring an empty string res = ""; for i in range(cols): for j in range(i, _len, cols + 1): # Adding the characters # into the empty string res += encodedText[j]; # If their any space at the end, # delete it while (res[len(res) - 1] == ' '): res = res[0: len(res) - 1]; return res; # Driver Code S = "GSRE E K EFGS KOE"; row = 4; print(decodeString(S, row)) # This code is contributed by Saurabh Jaiswal
C#
// C# program for the above approach
using System;
class GFG
{
// Function to find the desire string
static string decodeString(string encodedText, int rows)
{
// Stores the length of the string
int len = encodedText.Length;
// Stores the number of columns
int cols = len / rows;
// Declaring an empty string
string res = "";
for (int i = 0; i < cols; ++i) {
for (int j = i; j < len; j += cols + 1) {
// Adding the characters
// into the empty string
res += encodedText[j];
}
}
// If their any space at the end,
// delete it
while (res[res.Length - 1] == ' ') {
res = res.Remove(res.Length - 1);
}
return res;
}
// Driver Code
public static void Main()
{
string S = "GSRE E K EFGS KOE";
int row = 4;
Console.Write(decodeString(S, row));
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript code for the above approach
// Function to find the desire string
function decodeString(encodedText, rows) {
// Stores the length of the string
let len = encodedText.length;
// Stores the number of columns
let cols = Math.floor(len / rows);
// Declaring an empty string
let res = "";
for (let i = 0; i < cols; ++i)
for (let j = i; j < len; j += cols + 1)
// Adding the characters
// into the empty string
res += encodedText[j];
// If their any space at the end,
// delete it
while (res[res.length - 1] == ' ') {
res = res.slice(0, res.length - 1);
}
return res;
}
// Driver Code
let S = "GSRE E K EFGS KOE";
let row = 4;
document.write(decodeString(S, row))
// This code is contributed by Potta Lokesh
</script>
GEEKS FOR GEEKS
Complejidad de tiempo : O(M*(M/col)) que está cerca de O(longitud de la string)
Espacio auxiliar : O(N)