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 3
Output:
array output should be: "peotrrdvlpruoiloeeta"
Visualization of writing elements in zigzag fashion:
Visualization of writing output in the array:
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
We can solve this with the help of “interval” and “step”. The relation is shown in the below diagram.
Interval is the difference between the 2 vertical lines.
A step is a 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 the 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
Zanjo
My implementation : https://pastebin.com/S7xaxy6N