6. ZigZag Conversion

Description:

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 text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

Solutions:

If we read the characters in zigzag way, we will find the row numbers periodically
repeat. For rownumber > 1, the period is (rownumber-1)*2. For example, if rownumber = 6, s = "PAYPALISHIRINGAROUNDTHEWORLD", the pattern is

0  P         R         H
1  A       I I       T E
2  Y     H   N     D   W
3  P   S     G   N     O
4  A I       A O       R D
5  L         R         L

The row numbers repeat as "0 1 2 3 4 5 4 3 2 1", with length equal to 10 (= 5*2). It's not hard for us to find the repeated pattern, which starts from 0 to n-1 and then decreases to 1.
So, we can use a StringBuffer array sb to represent each line's string and read through the string and append the character to sb[0], sb[1], ..., sb[n-1], sb[n-2], ... sb[1] periodically. Meanwhile, an array is used to indicate which StringBuffer we shoud append to.

Here is the solution:

public class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1) return s;
        StringBuffer[] sb = new StringBuffer[numRows];
        // init sb
        for (int i = 0; i < numRows; i++) {
            sb[i] = new StringBuffer();
        }
        
        int period = (numRows-1)*2;
        int[] index = new int[period];
        // init index
        for (int i = 0; i <= period/2; i++) {
            index[i] = i;
        }
        for (int i = period-1, j = 1; i > period/2; i--) {
            index[i] = j++;
        }

        
        for (int i = 0; i < s.length(); i++) {
            sb[index[i%period]].append(s.charAt(i));
        }
        
        StringBuffer res = new StringBuffer();
        for (int i = 0; i < numRows; i++) {
            res = res.append(sb[i]);
        }
        
        return res.toString();
    }
}