#  ZigZag Conversion

#### Description

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

#### Required knowledge

###### What is ZigZag?
``````//if row is 2, its queue order are
0 3 4 7 8
1 2 5 6 9
//if row is 3, its queue order are
0   4   8
1 3 5 7 9
2   6
//if row is 4, its queue order are
0    6
1  5 7
2 4  8
3    9
``````
###### How to declare a dynamic 2-D array?

If the array type is char, you must initialize it as `'\0'`.

``````//char arr[m][n]
char** arr;
char* pData;
arr = (char **)malloc(m*sizeof(char*)+m*(n)*sizeof(char));
for (int i = 0, pData = (char*)(arr+m); i < m; i++, pData += (n)){
arr[i] = pData;
}
for(int i = 0 ; i < m; i++){
for(int j = 0 ; j < n; j++){
arr[i][j] = '\0';
}
}
``````

#### My solution

I create a 2-D array to locate the ZigZag pattern. To get its order, I don't have to do the same position with ZigZag. For example,

``````//if row is 4, its queue order are
0   6
1 5 7
2 4 8
3   9
``````

I combined elements between two long columns.

Another important thing is if you don't initialize 2-D array, you will get "Runtime Error"!

``````char* convert(char* s, int numRows) {
int size = strlen(s);
if ( numRows == 1 || size <= numRows )    return s;

int cols = size/(2*numRows-2);
cols = (size%(2*numRows-2) <= numRows)? 2*cols+1:2*cols+2;

//declare 2-D array
char** arr;
char* pData;
arr = (char **)malloc(numRows*sizeof(char*)+numRows*(cols)*sizeof(char));
for (int i = 0, pData = (char*)(arr+numRows); i < numRows; i++, pData += (cols)){
arr[i] = pData;
}
for(int i = 0 ; i < numRows ; i++){
for(int j = 0 ; j < cols ; j++){
arr[i][j] = '\0';
}
}

//reconstruct to ZigZag pattern
int pos = numRows-2;
for(int i = 0 ; i < size ; i++){
int idxR = i%(2*numRows-2);
int idxC = i/(2*numRows-2);
idxC = idxC*2;
if ( idxR <  numRows){
arr[idxR][idxC] = s[i];
//printf("%d %d\n", idxR, idxC);
}else{
arr[pos][idxC+1] = s[i];
//printf("%d %d\n", pos, idxC+1);
pos--;
if ( pos == 0 ){
pos = numRows-2;
}
}
}

//extract line by line in the order
int count = 0;
char* ans = (char*)malloc((size+1)*sizeof(char));
for(int i = 0 ; i < numRows ; i++){
for(int j = 0 ; j < cols ; j++){
//printf("%c", arr[i][j]);
if( arr[i][j] ){
ans[count++] = arr[i][j];
}
}
//printf("\n");
}

ans[count] = '\0';
free(arr);
return ans;
}
``````

#### Others solution

https://discuss.leetcode.com/topic/18545/8ms-c-solution-easy-to-understand

I thought that it's a math problem: How to transfer its relation for programming.

``````char* convert(char* s, int numRows) {
int n=strlen(s);
char* a;
int k=0;
if(numRows==1 || n<=numRows)return s;
for(int i=0;i<numRows;i++)
{
for(int j=i;j<n;j+=2*(numRows-1))
{
a[k++]=s[j];
if(i!=0 && i!=numRows-1)
{
int t=j+2*(numRows-1)-2*i;
if(t<n)
a[k++]=s[t];
}
}
}
a[k]='\0';
return a;
}
``````