[6] ZigZag Conversion

© Jarvus Chen / www.jarvus.net

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;
}