======================================
Problem Statement:
======================================
The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
P A H N A P L S I I G Y I R
And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:
string convert(string s, int numRows);
Example 1:
Input: s = "PAYPALISHIRING", numRows = 3 Output: "PAHNAPLSIIGYIR"
Example 2:
Input: s = "PAYPALISHIRING", numRows = 4 Output: "PINALSIGYAHRPI" Explanation: P I N A L S I G Y A H R P I
Example 3:
Input: s = "A", numRows = 1 Output: "A"
======================================
Solution:
======================================
Zig zag conversion algorithm deals with string traversal and index manipulation of rows while moving in forward and backward direction.
The below algorithm solves the problem in O(N) time complexity and O(N) space complexity.
1. Initialize numRows output list string array ( / string list ) to empty strings.
2. Traverse the input string and append each character to “currentRow”th string.
3. And increment the row until the row reaches the numRows limit and when the max limit( numRows ) is reached reverse the direction of row increment ( decrement the row ).
4. And keep on decrementing the row until the row reaches the minRows limit ( -1 ) and when the minLimit is reached reverse the direction of row decrement ( increment the row ).
5. Repeat the steps 3 & 4 until the end of String Input is reached.
6. After breaking out of the loop, initialize result string and add each of the outputList’s string to arrive at the solution.
Code for this Solution can be found @ Zigzag Conversion – LeetCode.
LeetCode Algorithms Solved 