 [English ver]

6. ZigZag Conversion

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)

And then read line by line: “PAHNAPLSIIGYIR”
Write the code that will take a string and make this conversion given a number of rows:

convert(“PAYPALISHIRING”, 3) should return “PAHNAPLSIIGYIR”.

First we need to know the meaning about the zigzag pattern, it means a pattern made up of small corners at variable angles, though constant within the zigzag, tracing a path between two parallel lines; it can be described as both jagged and fairly regular. In the begining i think it’s one line in the middle and then some symmetry verticle line between the middle horizontal line,when the number of rows is 4(use number to represent the index of the String)it would look like that:

but the trueth is not , it should be looked like that:

Approach 1 use String[]: Analysis
This method put every line’s String into the String[i] accordingly,in the last concate it together and then we get the result we want . When the position is in the first row , next time the position should move down,so step = 1.When the position is in the last Row , next time the position should move up , so the step = -1.

Time complexity ： O(n) 。n is the length of the string.
Space complexity ： O(n) .

Approach 2 StringBuilder[]: Analysis
This method’s principle is the same as the Approach 1 , it just replace the String into StringBuilder,it has a big optimization.

Time complexity ： O(n) 。n is the length of the string.
Space complexity ： O(n) .

Approach 3 use interval

Analysis

This method used regular interval to calculate position .

Time complexity ： O(n) 。n is the length of the string.
Space complexity ： O(n) .

If you have any suggestions to make the logic and implementation more better , or you have some advice on my description. Please let me know!Thanks!