Problem Explanation:
Given a string “prodevelopertutorial” and number of rows is 3. Write the string in a zigzag pattern.
Example:
Input: string = “prodevelopertutorial”. Number of rows 3Output:
Visualization of writing elements in zigzag fashion:
Visualization of writing output in the array:
Solution Explanation:
The zigzag pattern of the array elements by taking the index will be like:
0 4 8 12 16
1 3 5 7 9 11 13 15 17 19
2 6 10 14 18
Interval is the difference between the 2 vertical lines.
Step is the difference between the middle element at the vertical line.
In our example,
Interval between the 2 vertical column is 4. i.e 4 – 0 = 4, or 8 – 4 = 4
Step is 3 -1 = 2, 7 -5 = 2.
So we can come to a conclusion to a formula as shown below:
Interval = 2n – 2. Where n is number of rows
Step = interval – 2i. where “i” is the index.
Working of algorithm:
One for loop for each row
For each row, calculate the step.
Then for each character in that row, we place it in correct vertical columns.
[From the diagram, we know that for each column, the numbers increment sequentially except for the middle element.]
if we find a correct middle element, place it correctly.
The time complexity for this algorithm will be O( n ). Many will be confused because we are using 2 for loops the time complexity is O(n^2). But if you follow the solution correctly, we are visiting each node only once and are not repeating.
Solution in C++
#include<iostream>
#include <string>
using namespace std;
void zigzagConvert(string input_string, int num_of_rows)
{
int step = 0; // to hold calcualted step value
int interval = 0; // to hold calcualted interval value
int i = 0; // for outer for loop
int j = 0; // for inner for loop
int lenghtOfString = input_string.size(); // get the lenght of the string
string output_string; // to hold output string
int count = 0; // for counting number of characters in output string
if (num_of_rows <= 1 || num_of_rows > input_string.size())
{
cout<< endl<< input_string <<endl;
return;
}
interval = 2 * num_of_rows - 2; //calculate size of interval
for (i = 0; i < num_of_rows; ++i) // for each element in a row
{
step = interval - 2 * i; // calculate step for each row as it is dependent on index
for ( j = i; j < lenghtOfString; j+= interval) // place the element in the correct column
{
output_string += input_string [j];
count ++;
// get the middle element
if(step > 0 && step < interval && j + step < lenghtOfString)
{
output_string += input_string[ j + step];
count++;
}
}
}
cout<< endl<< "The input string is = "<<input_string <<endl;
cout<< endl<< "The result is = "<<output_string <<endl;
}
int main()
{
string input_string = "prodevelopertutorial";
int num_of_rows = 3;
zigzagConvert(input_string, num_of_rows);
//convert(input_string, num_of_rows);
return 0;
}
Output:
The input string is = prodevelopertutorial
The result is = peotrrdvlpruoiloeeta