Convert String to ZigZag Bottom Up

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/

Problem

Example

Solution

Method 1 - Use list to save the substrings

Method 2 - Append the character on the fly

See also