Dada una string y un número de filas ‘n’. Imprima la string formada al concatenar n filas cuando la string de entrada se escribe en forma de Zig-Zag por filas.
Ejemplos:
Input: str = "ABCDEFGH"
n = 2
Output: "ACEGBDFH"
Explanation: Let us write input string in Zig-Zag fashion
in 2 rows.
A C E G
B D F H
Now concatenate the two rows and ignore spaces
in every row. We get "ACEGBDFH"
Input: str = "GEEKSFORGEEKS"
n = 3
Output: GSGSEKFREKEOE
Explanation: Let us write input string in Zig-Zag fashion
in 3 rows.
G S G S
E K F R E K
E O E
Now concatenate the two rows and ignore spaces
in every row. We get "GSGSEKFREKEOE"
Le recomendamos encarecidamente que haga clic aquí y lo practique antes de pasar a la solución.
La idea es atravesar la string de entrada. Cada personaje tiene que ir a una de las filas. Uno por uno agregue todos los caracteres a diferentes filas. A continuación se muestra el algoritmo:
1) Create an array of n strings, arr[n] 2) Initialize direction as "down" and row as 0. The direction indicates whether we need to move up or down in rows. 3) Traverse the input string, do following for every character. a) Append current character to string of current row. b) If row number is n-1, then change direction to 'up' c) If row number is 0, then change direction to 'down' d) If direction is 'down', do row++. Else do row--. 4) One by one print all strings of arr[].
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to print string obtained by concatenation
// of different rows of Zig-Zag fashion
#include<bits/stdc++.h>
using namespace std;
// Prints concatenation of all rows of str's Zig-Zag fashion
void printZigZagConcat(string str, int n)
{
// Corner Case (Only one row)
if (n == 1)
{
cout << str;
return;
}
// Find length of string
int len = str.length();
// Create an array of strings for all n rows
string arr[n];
// Initialize index for array of strings arr[]
int row = 0;
bool down; // True if we are moving down in rows,
// else false
// Traverse through given string
for (int i = 0; i < len; ++i)
{
// append current character to current row
arr[row].push_back(str[i]);
// If last row is reached, change direction to 'up'
if (row == n-1)
down = false;
// If 1st row is reached, change direction to 'down'
else if (row == 0)
down = true;
// If direction is down, increment, else decrement
(down)? (row++): (row--);
}
// Print concatenation of all rows
for (int i = 0; i < n; ++i)
cout << arr[i];
}
// Driver program
int main()
{
string str = "GEEKSFORGEEKS";
int n = 3;
printZigZagConcat(str, n);
return 0;
}
Java
// Java program to print string
// obtained by concatenation
// of different rows of
// Zig-Zag fashion
import java.util.Arrays;
class GFG {
// Prints concatenation
// of all rows of str's
// Zig-Zag fashion
static void printZigZagConcat(String str,
int n)
{
// Corner Case (Only one row)
if (n == 1)
{
System.out.print(str);
return;
}
char[] str1 = str.toCharArray();
// Find length of string
int len = str.length();
// Create an array of
// strings for all n rows
String[] arr = new String[n];
Arrays.fill(arr, "");
// Initialize index for
// array of strings arr[]
int row = 0;
boolean down = true; // True if we are moving
// down in rows, else false
// Traverse through
// given string
for (int i = 0; i < len; ++i)
{
// append current character
// to current row
arr[row] += (str1[i]);
// If last row is reached,
// change direction to 'up'
if (row == n - 1)
{
down = false;
}
// If 1st row is reached,
// change direction to 'down'
else if (row == 0)
{
down = true;
}
// If direction is down,
// increment, else decrement
if (down)
{
row++;
}
else
{
row--;
}
}
// Print concatenation
// of all rows
for (int i = 0; i < n; ++i)
{
System.out.print(arr[i]);
}
}
// Driver Code
public static void main(String[] args)
{
String str = "GEEKSFORGEEKS";
int n = 3;
printZigZagConcat(str, n);
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python 3 program to print # string obtained by # concatenation of different # rows of Zig-Zag fashion # Prints concatenation of all # rows of str's Zig-Zag fashion def printZigZagConcat(str, n): # Corner Case (Only one row) if n == 1: print(str) return # Find length of string l = len(str) # Create an array of # strings for all n rows arr=["" for x in range(l)] # Initialize index for # array of strings arr[] row = 0 # Traverse through # given string for i in range(l): # append current character # to current row arr[row] += str[i] # If last row is reached, # change direction to 'up' if row == n - 1: down = False # If 1st row is reached, # change direction to 'down' elif row == 0: down = True # If direction is down, # increment, else decrement if down: row += 1 else: row -= 1 # Print concatenation # of all rows for i in range(n): print(arr[i], end = "") # Driver Code str = "GEEKSFORGEEKS" n = 3 printZigZagConcat(str, n) # This code is contributed # by ChitraNayal
C#
// C# program to print string
// obtained by concatenation
// of different rows of
// Zig-Zag fashion
using System;
class GFG
{
// Prints concatenation
// of all rows of str's
// Zig-Zag fashion
static void printZigZagConcat(string str,
int n)
{
// Corner Case (Only one row)
if (n == 1)
{
Console.Write(str);
return;
}
char[] str1 = str.ToCharArray();
// Find length of string
int len = str.Length;
// Create an array of
// strings for all n rows
string []arr = new string[n];
// Initialize index for
// array of strings arr[]
int row = 0;
bool down = true; // True if we are moving
// down in rows, else false
// Traverse through
// given string
for (int i = 0; i < len; ++i)
{
// append current character
// to current row
arr[row] += (str1[i]);
// If last row is reached,
// change direction to 'up'
if (row == n - 1)
down = false;
// If 1st row is reached,
// change direction to 'down'
else if (row == 0)
down = true;
// If direction is down,
// increment, else decrement
if(down)
row++;
else
row--;
}
// Print concatenation
// of all rows
for (int i = 0; i < n; ++i)
Console.Write(arr[i]);
}
// Driver Code
public static void Main()
{
String str = "GEEKSFORGEEKS";
int n = 3;
printZigZagConcat(str, n);
}
}
// This code is contributed
// by ChitraNayal
Javascript
<script>
// Javascript program to print string
// obtained by concatenation
// of different rows of
// Zig-Zag fashion
// Prints concatenation
// of all rows of str's
// Zig-Zag fashion
function printZigZagConcat(str,n)
{
// Corner Case (Only one row)
if (n == 1)
{
document.write(str);
return;
}
let str1 = str.split("");
// Find length of string
let len = str.length;
// Create an array of
// strings for all n rows
let arr = new Array(n);
for(let i=0;i<n;i++)
{
arr[i]="";
}
// Initialize index for
// array of strings arr[]
let row = 0;
let down = true; // True if we are moving
// down in rows, else false
// Traverse through
// given string
for (let i = 0; i < len; ++i)
{
// append current character
// to current row
arr[row] += (str1[i]);
// If last row is reached,
// change direction to 'up'
if (row == n - 1)
{
down = false;
}
// If 1st row is reached,
// change direction to 'down'
else if (row == 0)
{
down = true;
}
// If direction is down,
// increment, else decrement
if (down)
{
row++;
}
else
{
row--;
}
}
// Print concatenation
// of all rows
for (let i = 0; i < n; ++i)
{
document.write(arr[i]);
}
}
// Driver Code
let str = "GEEKSFORGEEKS";
let n = 3;
printZigZagConcat(str, n);
// This code is contributed by ab2127
</script>
Producción
GSGSEKFREKEOE
Complejidad de tiempo: O (len) donde len es la longitud de la string de entrada.
Espacio auxiliar: O(len)
Gracias a Gaurav Ahirwar por sugerir la solución anterior.
Otro enfoque:
si asumimos que estamos iterando a través de una array imaginaria de recuento de filas n uno por uno e imprimiendo caracteres
para la primera y la última fila, el índice se incrementará en un valor de i+= 2*(n-1)
para las filas intermedias, si vamos en dirección ascendente, el índice se incrementará como i+= 2*(n-rowNum-1), y para la dirección descendente, el índice se incrementará como 2*rowNum. A continuación se muestra la implementación de trabajo. en JAVA
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program for above approach
#include<bits/stdc++.h>
using namespace std;
// Function for zig-zag Concatenation
string zigZagConcat(string s, int n)
{
// Check is n is less
// or equal to 1
if (n <= 1)
{
return s;
}
string result = "";
// Iterate rowNum from 0 to n - 1
for (int rowNum = 0; rowNum < n; rowNum++)
{
int i = rowNum;
bool up = true;
// Iterate i till s.length() - 1
while (i < s.length())
{
result += s[i];
// Check is rowNum is 0 or n - 1
if (rowNum == 0 || rowNum == n - 1)
{
i += (2 * n - 2);
}
else
{
if (up)
{
i += (2 * (n - rowNum) - 2);
}
else
{
i += rowNum * 2;
}
up ^= true;
}
}
}
return result;
}
// Driver Code
int main()
{
string str = "GEEKSFORGEEKS";
int n = 3;
cout<< zigZagConcat(str, n);
}
// This code is contributed by Mayank Tyagi
Java
// Java Program for above approach
import java.lang.*;
class Solution
{
// Function for zig-zag Concatenation
private static String zigZagConcat(
String s, int n)
{
// Check is n is less
// or equal to 1
if (n <= 1)
{
return s;
}
StringBuilder result = new
StringBuilder();
// Iterate rowNum from 0 to n - 1
for (int rowNum = 0; rowNum < n; rowNum++)
{
int i = rowNum;
boolean up = true;
// Iterate i till s.length() - 1
while (i < s.length())
{
result = result.append(s.charAt(i));
// Check is rowNum is 0 or n - 1
if (rowNum == 0 || rowNum == n - 1)
{
i += (2 * n - 2);
}
else
{
if (up)
{
i += (2 * (n - rowNum) - 2);
}
else
{
i += rowNum * 2;
}
up ^= true;
}
}
}
return result.toString();
}
// Driver Code
public static void main(String[] args)
{
String str = "GEEKSFORGEEKS";
int n = 3;
System.out.println(zigZagConcat(str, n));
}
}
// This code is contributed by Sakshi Sachdeva
Python3
# Python Program for above approach # Function for zig-zag Concatenation def zigZagConcat(s, n): # Check is n is less # or equal to 1 if (n <= 1): return s result = "" # Iterate rowNum from 0 to n - 1 for rowNum in range(n): i = rowNum up = True # Iterate i till s.length() - 1 while(i < len(s)): result += s[i] # Check is rowNum is 0 or n - 1 if (rowNum == 0 or rowNum == n - 1): i += (2 * n - 2) else: if(up): i += (2 * (n - rowNum) - 2) else: i += rowNum * 2 up ^= True return result # Driver Code str = "GEEKSFORGEEKS" n = 3 print(zigZagConcat(str, n)) # This code is contributed by rag2127
C#
// C# Program for above approach
using System;
public class GFG{
// Function for zig-zag Concatenation
static string zigZagConcat( string s, int n)
{
// Check is n is less
// or equal to 1
if (n <= 1)
{
return s;
}
string result="";
// Iterate rowNum from 0 to n - 1
for (int rowNum = 0; rowNum < n; rowNum++)
{
int i = rowNum;
bool up = true;
// Iterate i till s.length() - 1
while (i < s.Length)
{
result += s[i];
// Check is rowNum is 0 or n - 1
if (rowNum == 0 || rowNum == n - 1)
{
i += (2 * n - 2);
}
else
{
if (up)
{
i += (2 * (n - rowNum) - 2);
}
else
{
i += rowNum * 2;
}
up ^= true;
}
}
}
return result;
}
// Driver Code
static public void Main (){
string str = "GEEKSFORGEEKS";
int n = 3;
Console.WriteLine(zigZagConcat(str, n));
}
}
// This code is contributed by avanitrachhadiya2155
Javascript
<script>
// Javascript Program for above approach
// Function for zig-zag Concatenation
function zigZagConcat(s,n)
{
// Check is n is less
// or equal to 1
if (n <= 1)
{
return s;
}
let result = [];
// Iterate rowNum from 0 to n - 1
for (let rowNum = 0; rowNum < n; rowNum++)
{
let i = rowNum;
let up = true;
// Iterate i till s.length() - 1
while (i < s.length)
{
result.push(s[i]);
// Check is rowNum is 0 or n - 1
if (rowNum == 0 || rowNum == n - 1)
{
i += (2 * n - 2);
}
else
{
if (up)
{
i += (2 * (n - rowNum) - 2);
}
else
{
i += rowNum * 2;
}
up ^= true;
}
}
}
return result.join("");
}
// Driver Code
let str = "GEEKSFORGEEKS";
let n = 3;
document.write(zigZagConcat(str, n));
// This code is contributed by unknown2108
</script>
Producción
GSGSEKFREKEOE
Complejidad de tiempo: O (longitud)
Complejidad espacial: O(1)
Gracias a Sakshi Sachdeva por sugerir la solución anterior.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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