[LeetCode] 6. ZigZag Conversion

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



1. Element manipulation.
 Special boarder condition on first row and last row
 Special boarder condition on 1 row.
 Alternative increment, see initial increment to the second step first, will be changed to step 1.
 Better way is to setup index,

public class Solution {
    public String convert(String s, int numRows) {
        int len = s.length();
        
        StringBuilder sb = new StringBuilder();
        if(0 == len)
            return sb.toString();
        
        if(1 == numRows){
            return s;
        }
        
        for(int j = 0; j < numRows; ++j){
            
            int d1 = 2*(numRows - 1 - j);
            int d2 = 2*j;
            
            if(0 == d1){
                for(int i = j; i < len; i += d2){
                    sb.append(s.charAt(i));
                }
            }
            else if(0 == d2){
                for(int i = j; i < len; i += d1){
                    sb.append(s.charAt(i));
                }
            }
            else{
                int d = d2;
                for(int i = j; i < len; i += d){
                    sb.append(s.charAt(i));
                    if(d == d1)
                        d = d2;
                    else
                        d = d1;
                }
            }
            
        }
        
        return sb.toString();
        
    }
}

2. The following code works as well, the condition of the last row matches with middle rows, special handling of the first row, first element is OK.

public class Solution {
    public String convert(String s, int numRows) {
        int len = s.length();
        
        StringBuilder sb = new StringBuilder();
        if(0 == len)
            return sb.toString();
        
        sb.append(s.charAt(0));
        
        if(1 == numRows){
            return s;
        }
        
        for(int j = 0; j < numRows; ++j){
            int d1 = 2*(numRows - 1 - j);
            int d2 = 2*j;
            
            int d = d2;
            
            for(int i = j; i < len; i += d){
                if(0 != d){
                    sb.append(s.charAt(i));
                }
                if(d == d1)
                    d = d2;
                else
                    d = d1;
            }
        }
        
        return sb.toString();
        
    }
}

3. A more efficient code It turns out, set up a variable to judge the past increment value seems to be the leanest code. Might not be the most efficient one. It is similar to set a prehead in list manipulation. From somewhere before the list, from somewhere before the array.

public class Solution {
    public String convert(String s, int numRows) {
        int len = s.length();
        
        StringBuilder sb = new StringBuilder();
        if(0 == len)
            return sb.toString();
        
        if(1 == numRows){
            return s;
        }
        
        for(int j = 0; j < numRows; ++j){
            
            int d1 = 2*(numRows - 1 - j);
            int d2 = 2*j;

            int[] inc = new int[2];
            inc[0] = d1;
            inc[1] = d2;
                
            int index = 0;
            int add = -1;
            for(int i = j; i < len; i += inc[index++%2]){
                if(0 != add)
                    sb.append(s.charAt(i));
                add = inc[index%2];
            }
        }
        
        return sb.toString();
        
    }
}