Leetcode - 6. ZigZag Conversion ( Tutorial + Solution in C)

=>Try Yourself First. For help Scroll Down.

Problem Link: https://leetcode.com/problems/zigzag-conversion/

Problem Clearance: In this problem, you will be given a string. You have to design the string in a zigzag pattern. The zigzag pattern will follow the number of given rows.  After that, you will collect the characters row-wise and then return the resultant string. The following example will be helpful to understand the problem clearly. Suppose the given string is "PAYPALISHIRING". You are given the number of rows like 3 and 4. See the following image -

You can see the coordination of characters when the number of rows is 3 and 4. For numRows = 3, if we collect the characters by row number 1, 2, and 3 sequentially we will have "PAHNAPLSIIGYIR". And for numRows = 4, when we collect the characters by row number 1, 2, 3, and 4 sequentially we will have "PINALSIGYAHRPI". 

The legs of the ZIGZAG will be straight that is, for numRows = 3, {"PAY", "ALI", "HIR", "NG"}  will be written in one single column and for numRows = 4, {"PAYP", "ISHI", "NG"} will be written in one single column. The length of the string and the number of rows can be at most 1000. 

Required Knowledge: Implementation

Tutorial: For this problem, we just have to control our movement through the zigzag. In the mentioned zigzag, we have two types of movement. One is moving straight down and the other is moving right diagonally up.

We will take a matrix of size 1000x1000. At the beginning of each test case, we will fill the resultant matrix (say MAT[][]) with a character that will not be in the input string. I am considering '#' as a null character in this case.  Now for each character of the given string, we will either go straight down or go right diagonally up. 

For moving straight down, we will just increase the row number keeping the column number as it is. That is for the i^th character of the given string, it will be filled in MAT[current_row + 1][current_column].  We will continue moving until the current row count will be equal to the given numbers. Once our current row count is equal to the numRows we will change our movement.

For moving right diagonally up, we will decrease the row count by one and increase the column count by one. That is for the i^th character of the given string, it will be filled in MAT[current_row - 1][current_column + 1]. We will continue moving until the current row count will be equal to 1. Once we hit the current row count to 1, we will change our movement. 

Now just parse each cell of the resultant matrix and concatenate the character resides in that cell except '#'. Return the final string.

Pretty simple, right? That's all. You can see the implementation if you want to.

Tip: If you are getting Time Limit Exceeded that might be the reason for traversing the resultant matrix, MAT with 10⁶ cells twice for multiple test cases. You can lower down the row count to numRows and the column count to (length_of_string/numRows) + (length_of_string/numRows) * (numRows - 2). Now think why this works? If you can not get it leave a comment. 

Code:

char map[1005][1005];

int mstrlen(char *s){
    int i = 0;
    for(;s[i];i++);
    return i;
}

char * convert(char * s, int numRows){
    if(numRows == 1) return s;
    int len = mstrlen(s);
    int toR = numRows, toC = (len/numRows) + (len/numRows) * (toR - 2);
    for(int i=0; i<=toR; i++){
        for(int j=0; j<= toC; j++){
            map[i][j] = '#';
        }
    }
    
    //printf("H %s\n", s);
    
    int i = 0, row = 0, column = 0, recent_r, recent_c; 
    bool goS = true;
    while(s[i]!='\0'){
        map[row][column] = s[i];
        recent_r = row, recent_c = column;
        i++;
        if(goS){
            row++; 
            if(row >= numRows){
                row = recent_r - 1;
                column = recent_c + 1;
                goS = false;
            }
        }
        else{
            row--; column++;
            if(row < 0){
                row = recent_r + 1;
                column = recent_c;
                goS = true;
            }
        }
    }
    char * res; int idx  = 0;
    res = (char *) malloc(sizeof(char) * 1005);
    for(int i=0; i<=toR; i++){
        for(int j=0; j<=toC; j++){
            if(map[i][j]!='#'){
                res[idx++] = map[i][j];
                //printf("%d, %d = %c\n",i, j, map[i][j]);
            }
        }
    }
    res[idx] = '\0';
    return res;
}

=> Leave a comment if you have anything to share. Thank you.