[LeetCode] ZigZag Conversion (Java)

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".


The number of rows is variable. So we need to find the rule of each row. For example, when nRows = 4, we know the ZigZag should be like the following.

It’s easy to find that the step of 4-number column is 6. In fact, the step is just two times of nRows minus 2, in which 2 indicating there  are no numbers between the 4-number column in the first line and last line.

And there is only one number between 4-number column in other lines. Take the second line as an example. The second line is “1 5 7 11 13 17 19”. We can take a look at “1 5 7”. The step between “1” and “5” is (nRows – 1 – 1) * 2, which is 4. And the step of “5” and “7” is 6 – 4 = 2. In fact, assuming we are at line i (starting at 0), the first step is (nRows – 1 – i) * 2.


We should be careful about the situation when nRows = 1. Because our formula is not suitable when nRows = 1. And the inner loop should start from i, not 0.


We only visit each character in s once. So the complexity is only $O(n)$.