Convert String to ZigZag Bottom Up

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/zigzag-conversion-problem/.

Problem

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)

Example

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

Solution

Method 1 - Use list to save the substrings

A straightforward solution is to actually build up the zigzag character matrix and read the matrix into a string.
Here is the basic algo:

• Maintain down boolean which tells whether you are going up or down in zig zag order.
• As soon as rows = 0 means you need to go down now and as soon as rows = nRows - 1 you need to go up now
• Just keep on doing this until whole string is exhausted
• Using StringBuilder list/array to store elements in zig zag order and in the end just append all characters from each StringBuilder to return output.

Here is the code in java:

import java.util.ArrayList;

public class Solution {
    public String convert(String s, int nRows) {
        if(s == null || s.length() <= 1 || nRows <= 1){
            return s;
        }
        
        ArrayList<StringBuilder> list = new ArrayList<StringBuilder>();
        for(int i = 0; i < nRows; i++){
            list.add(new StringBuilder());
        }
        
        int i = 0;
        boolean down = false;
        int row = 0;
        
        while(i < s.length()){
            list.get(row).append(s.charAt(i));
            if(row == 0){
                down = true;
            }else if(row == nRows - 1){
                down = false;
            }
            
            if(down){
                row++;
            }else{
                row--;
            }
            
            i++;
        }
        
        i = 0;
        StringBuilder output = new StringBuilder();
        while( i < list.size()){
            output.append(list.get(i).toString());
            i++;
        }
        return output.toString();
    }
}

Though time complexity is good O(n), but the space is complexity is O(nRows*Max_column_in_a_row) = O(n)

Method 2 - Append the character on the fly

Another way is to calculate the corresponding index on the fly and append the character into a string.
Take convert("PAYPALISHIRING", 4) as an example. The matrix will look as follows :

P   I   N
A L S I G
Y A H R
P   I

which can be expended as below (You will see why we rewrite like this soon.).

P   I   N
A   S   G
Y   H
P   I
A   R
L   I

Some useful properties:

• For any full columns, the odd ones have nRows characters, even ones have (nRows - 2) characters.
• For the first and last rows, we read one single character from each expended column;
• For the rest of rows, we read two characters, one from top part and one from bottom part, from each expended column.
• One edge case is that nRows = 1, where (nRows*2 - 2) becomes 0. In this case, we should simply return the original string.

public String convert(String s, int nRows) {  
  if (nRows == 1) return s;  
  
  StringBuilder ss = new StringBuilder();  
  int n = nRows + nRows - 2;  
  // rest rows  
  for (int i = 0; i < nRows; ++i) {  
    int cur = i;  
    while (cur < s.length()) {  
      ss.append(s.charAt(cur));  
      cur += n;  
      if (i > 0 && i < nRows - 1 && (cur - i - i) < s.length()) {  
        ss.append(s.charAt(cur - i - i));  
      }  
    }  
  }  
  return ss.toString();  
}  

Thanks.
Reference
http://www.params.me/2014/04/leetcode-zigzag-conversion-in-java.html
http://n00tc0d3r.blogspot.in/2013/06/zigzag-conversion.html
https://leetcode.com/problems/zigzag-conversion/