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 conver…

ZigZagConvertion.java

/*
 * Time complexity : O(n), Space Complexity : O(n), 
 * We could just use a n size char array instead of using nRows' StringBuilder array. See the convert0 for the detail
 */
public static String convert(String s, int nRows){
    if (s == null || s.length() <= 1 || nRows <= 1)
        return s;
    StringBuilder[] sbs = new StringBuilder[nRows];

    for (int i=0; i<nRows; i++){
        sbs[i] = new StringBuilder();
    }
    int i = 0, n = s.length(), m = 2*(nRows - 1);
    while (i < n){
        int j = 0, cnt = 0;
        while (cnt < m && i < n){
            sbs[j].append(s.charAt(i++));
            if (cnt < nRows - 1)
                j++;
            else
                j--;
            cnt++;
        }
    }
    for (i=1; i<nRows; i++)
        sbs[0].append(sbs[i].toString());
    return sbs[0].toString();
}

public static String convert0(String s, int nRows){
    if (s == null || s.length() <= 1 || nRows <= 1)
        return s;
    int n = s.length();
    char[] chs = new char[n];
    int m = 2*(nRows - 1);
    for (int i = 0, j = 0; i<nRows; i++){ // i : row index [0 .. nRows-1]  , j : index of char array, [0..n-1]
        for (int k = i; k < n; k += m){
            chs[j++] = s.charAt(k);
            if (i > 0 && i < nRows - 1 && (k + m - 2*i) < n)
                chs[j++] = s.charAt(k + m - 2*i);
        }
    }
    return new String(chs);
}