### leetcode Question 125: ZigZag Conversion

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

Analysis:
The idea is straightforward. Use a 2-D vector storing the zigzag sequence, for every element in the string, put it into proper position. Then output.
There are two major steps to put element into its position:
(1).  Write # of nRows chars into the same column. like " | "
(2).  Write # of nRows-2 chars into different column and rows in reverse diagonal order.   like " / ".

e.g.
Input: PAYPALISHIRING

2D vector:
0  1  2 3 4  5 6  7
-------------------
0 | P         I         N
1 | A     L S     I  G
2 | Y  A   H  R
3 | P         I

### (updated 201309):

Note:  "ABCD" is    A  C
| / |
B  D

### Code:

class Solution {
public:
string convert(string s, int nRows) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector<string> zz(nRows,"");
if (nRows==1){return s;}

int i=0; //for string
int r=0; //for zz vector
bool zig = false; // if s[i] is in "/" or "|" direction
while (i<s.size()){
if (r<nRows && !zig){
zz[r]+=s[i];
r++;
i++;
}else{
if (!zig){
zig=true;
r--;
}else{
r--;
zz[r] = zz[r]+s[i];
if (r==0){zig=false;r++;}
i++;
}
}
}
string res; //get result;
for (int i=0;i<zz.size();i++){
for (int j=0;j<zz[i].size();j++){
res = res+ zz[i][j];
}
}
return res;
}
};


(old version)Code:

class Solution {
public:

string printStr(vector<vector<char> > &t, int col,int nRow){
string str="";
for (int j=0;j<nRow;j++){
for (int i =0; i<=col;i++){
if (t[j][i]!='#'){
str = str+ t[j][i];
}
}
}
return str;
}

string convert(string s, int nRows) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if ((nRows<=0) || (s.size()==0)){return "";}
if (nRows==1) {return s;}
if (nRows>=s.size()){return s;}
int k=s.size();
vector<vector<char> > t(nRows,vector<char>(k,'#'));
int len = s.size();
int col = 0;
int row = 0;
int count = 0;
while(count < len){
if (row<nRows){
t[row][col]=s[count];
row++;
count++;
}else{
col++;
for (int j = nRows-2; j>=1;j--){
t[j][col]=s[count];
count ++;
if (count>=len){ return  printStr(t,col,nRows);}
col++;
}
row = 0;
}
}
return printStr(t,col,nRows);
}
};


1. class Solution {
public:
string convert(string s, int nRows) {
int n=s.size();
if(n==0) return "";
if(nRows==1)
return s;
int half = nRows-1;
int step = half*2;
string ret="";

vector v(nRows,"");

for(int i=0; i<n; i+=step)
{
for(int j=0; j<half; j++)
if(i+j<n) v[j]+=s[i+j];
for(int j=0; j<half; j++)
if(i+half+j<n) v[half-j]+=s[i+half+j];
}
for(int i=0; i<nRows; i++)
ret+=v[i];
return ret;
}
};

2. For this problem, using a little bit math to figure out the index increment of each row seems to provide a more simplified solution, here is my code (no need to maintain a 2D vector for storing intermediate results:

string convert(string s, int nRows) {
string res;
if(nRows==1) return s;
for(int i=0; i<nRows && i<s.size(); i++) {
int inc = 2*(nRows-i-1), cur = i, pre =-1;
while(cur<s.size()) {
if(cur!=pre) res.push_back(s[cur]);
pre = cur;
cur += inc;
inc = 2*(nRows-1)-inc;
}
}
return res;
}

1. thumbs up bro!!

2. same as I did.