Zigzag Conversion

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