Concatenación de strings en zig-zag en N filas

Posted on by Rudeus Greyrat

La string » PAYPALISHIRING » está escrita en un patrón de zigzag en un número determinado de filas como esta: (es posible que desee mostrar este patrón en una fuente fija para una mejor legibilidad)

P A H N
  A P L S I I G
    Y I R

Y luego lea línea por línea: PAHNAPLSIIGYIR .

Por lo tanto, para una string str dada y un número entero N , la tarea es imprimir la string formada al concatenar N filas cuando str se escribe en forma de Zig-Zag por filas.

Ejemplo:

Entrada: str = “PAYPALISHIRING”, N = 3
Salida: PAHNAPLSIIGYIR

Entrada: str = “ABCDEFGH”, N = 2
Salida: ACEGBDFH
Explicación: La string de entrada se puede escribir en forma de Zig-Zag en 2 filas de la siguiente manera:
A C E G    
   B D F H
Por lo tanto, al leer el patrón anterior por filas, la string de salida es “ACEGBDFH”

Enfoque: el problema dado es un problema basado en la implementación que se puede resolver siguiendo los pasos a continuación

  • Cree una array de N strings , arr[N] .
  • Inicialice la dirección como «abajo» y la fila como 0 . La dirección indica si el puntero actual se mueve hacia arriba o hacia abajo en filas.
  • Atraviese la string de entrada, haga lo siguiente para cada carácter.
    • Agregue el carácter actual a la string que representa la fila actual.
    • Si el número de fila es N – 1 , cambie la dirección a ‘arriba’
    • Si el número de fila es 0 , cambie la dirección a ‘abajo’
    • Si la dirección es ‘abajo’, haga fila ++. De lo contrario haz fila–.
  • Una por una imprime todas las strings de arr[] .

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that Prints concatenation of
// all rows of str's Zig-Zag fashion
void printZigZagConcat(string str, int n)
{
    if (n == 1)
    {
        cout << str << endl;
    }
    string res = "";
    string arr[n] = {""};
    bool down;
    int row = 0; // helps in building individual blocks of strings
 
    for (int i = 0; i < str.size(); i++)
    {
        arr[row].push_back(str[i]);
        if (row == n - 1)
        {
            down = false;
        }
        if (row == 0)
        {
            down = true;
        }
        if (!down)
            row--;
        else
            row++;
    }
 
    for (int i = 0; i < n; i++)
    {
        cout << arr[i];
    }
}
 
int main()
{
    // Driver Code
    string str = "PAYPALISHIRING";
    int N = 3;
    printZigZagConcat(str, N);
    return 0;
}
 
// This code is contributed by Potta Lokesh

Java

// Java code for the above approach
import java.util.*;
 
class GFG {
 
  // Function that Prints concatenation of
  // all rows of str's Zig-Zag fashion
  static void printZigZagConcat(String str, int n)
  {
    if (n == 1) {
      System.out.print(str + "\n");
    }
    String res = "";
    String[] arr = new String[n];
    for (int i = 0; i < n; i++)
      arr[i] = "";
    boolean down = false;
    int row = 0; // helps in building individual blocks
    // of Strings
 
    for (int i = 0; i < str.length(); i++) {
      if (row >= 0)
        arr[row] += (str.charAt(i));
      if (row == n - 1) {
        down = false;
      }
      if (row == 0) {
        down = true;
      }
      if (!down)
        row--;
      else
        row++;
    }
 
    for (int i = 0; i < n; i++) {
      System.out.print(arr[i]);
    }
  }
 
  public static void main(String[] args)
  {
    // Driver Code
    String str = "PAYPALISHIRING";
    int N = 3;
    printZigZagConcat(str, N);
  }
}
 
// This code is contributed by umadevi9616

Python3

# Python 3 program of the above approach
 
# Function that 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 = "PAYPALISHIRING"
N = 3
printZigZagConcat(str, N)

C#

// C# program to implement above approach
using System;
using System.Collections;
using System.Collections.Generic;
 
class GFG
{
 
  // Function that Prints concatenation of
  // all rows of str's Zig-Zag fashion
  static void printZigZagConcat(String str, int n)
  {
    if (n == 1) {
      Console.WriteLine(str);
    }
 
    String[] arr = new String[n];
    for (int i = 0 ; i < n ; i++)
      arr[i] = "";
 
    bool down = false;
    int row = 0; // helps in building individual blocks
    // of Strings
 
    for (int i = 0 ; i < str.Length ; i++) {
      if (row >= 0)
        arr[row] += (str[i]);
      if (row == n - 1) {
        down = false;
      }
      if (row == 0) {
        down = true;
      }
      if (!down)
        row--;
      else
        row++;
    }
 
    for (int i = 0; i < n; i++) {
      Console.Write(arr[i]);
    }
  }
 
 
  // Driver code
  public static void Main(string[] args){
 
    // Driver Code
    String str = "PAYPALISHIRING";
    int N = 3;
    printZigZagConcat(str, N);
 
  }
}
 
// This code is contributed by subhamgoyal2014.

JavaScript

<script>
    // JavaScript code for the above approach
 
    // Function that Prints concatenation of
    // all rows of str's Zig-Zag fashion
    const printZigZagConcat = (str, n) => {
        if (n == 1) {
            document.write(`${str}<br/>`);
        }
        let res = "";
        let arr = new Array(n).fill("");
        let down = false;
        let row = 0; // helps in building individual blocks of strings
 
        for (let i = 0; i < str.length; i++) {
            arr[row] += str[i];
            if (row == n - 1) {
                down = false;
            }
            if (row == 0) {
                down = true;
            }
            if (!down)
                row--;
            else
                row++;
        }
 
        for (let i = 0; i < n; i++) {
            document.write(arr[i]);
        }
    }
 
    // Driver Code
    let str = "PAYPALISHIRING";
    let N = 3;
    printZigZagConcat(str, N);
 
// This code is contributed by rakeshsahni
 
</script>
Producción

PAHNAPLSIIGYIR

Complejidad temporal: O(N)
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por Code_r y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *