# Zigzag Conversion

Difficulty Level Medium
StringViews 1406

In the Zigzag Conversion problem, we have given a string s of length n and an integer r representing the number of rows. Convert the given string in the zigzag pattern of r rows and concatenate the characters row-wise. Print the new concatenated string.

## Example

Input :

s = “TutorialCup”

r = 3

Output : TrCuoilutap

Input :

s = “Programming”

r = 4

Output : Pmramoriggn

## Explanation for Zigzag Conversion

Let string s = “TutorialCup” and the number of rows i.e. r = 3

Initialize a string array a[ ] of size r to form the zigzag pattern. Also, initialize an integer variable row to track the current row as 0 and a boolean variable down.

Start traversing the string and update the string array as follows. Below are steps for the above example –

• 1 : row = 0, down = true, a[ ] = T
• 2 : row = 1, down = true, a[ ] = T, u
• 3 : row = 2, down = false, a[ ] = T, u, t
• 4 : row = 1, down = true, a[ ] = T, uo, t
• 5 : row = 0, down = true, a[ ] = Tr, uo, t
• 6 : row = 1, down = true, a[ ] = Tr, uoi, t
• 7 : row = 2, down = false, a[ ] = Tr, uoi, ta
• 8 : row = 1, down = true, a[ ] = Tr, uoil, ta
• 9 : row = 0, down = true, a[ ] = TrC, uoil, ta
• 10 : row = 1, down = true, a[ ] = TrC, uoilu, ta
• 11 : row = 2, down = false, a[ ] = TrC, uoilu, tap

Therefore, the resulting string is TrCuoilutap

## Algorithm for Zigzag Conversion

1. Initialize a string s of length n and an integer r representing the number of rows.
2. If the given number of rows(r) is 1 return string.
3. Create an array of size r of string type.
4. Initialize row as 0 and down of boolean type.
5. Traverse from 0 to n-1 and store the characters of a string in string array at index row.
6. Check if the row is equal to r-1 update down as false.
7. Else if the row is 0 updates down as true.
8. If down is true increment the row else decrement the row.
9. Print the updated string array.

## C++ Program for zigzag conversion

```#include<bits/stdc++.h>
using namespace std;

void ZigZag(string s, int r){

if(r == 1){
cout<<s;
return;
}

int n = s.length();

string a[r];

int row = 0;
bool down;

for(int i=0; i<n; ++i){

a[row].push_back(s[i]);

if(row == r-1)
down = false;

else if (row == 0)
down = true;

(down)? (row++): (row--);
}

for(int i=0; i<r; ++i)
cout<<a[i];
}

int main(){
string s = "TutorialCup";
int r = 3;
ZigZag(s, r);
return 0;
}```
`TrCuoilutap`

## Java Program for zigzag conversion

```import java.util.Arrays;

class Concatenate{

static void ZigZag(String s, int r){

if(r == 1){
System.out.print(s);
return;
}

char[] str = s.toCharArray();

int n = s.length();

String[] a = new String[r];
Arrays.fill(a, "");

int row = 0;
boolean down = true;

for(int i=0; i<n; ++i){

a[row] += (str[i]);

if(row == r-1){
down = false;
}

else if(row == 0){
down = true;
}

if(down){
row++;
}
else{
row--;
}
}

for(int i=0; i<r; ++i){
System.out.print(a[i]);
}
}

public static void main(String[] args){

String s = "TutorialCup";
int r = 3;
ZigZag(s, r);

}
}```
`TrCuoilutap`

## Complexity Analysis for Zigzag Conversion

Time Complexity: O(n) where n is the size of the input string.

Auxiliary Space: O(n) because we store the answer in an array(of type string) while computing the answer.

References

Translate »