Analysis and Javascript Implementation


  • 0
    K

    Assuming that we need to print ABCDEFGH from 1 to 4 rows

    1 Row : ABCDEFGH - just return the string
    
    2 Rows :
    A C E G
    B D F H
    
    3 Rows :
    A   E  
    B D F H
    C   G 
    
    4 Rows
    A     G
    B   F H
    C E
    D   
    

    Except special case 1 row, we see that it reaches first row again after (rowsNum * 2 - 2) elements, i.e 6 for 4 rows, 4 for 3 rows, 2 for 2 rows.

    So we can divide the string into chunks of (rowsNum * 2 - 2) elements.
    In each chunk:

    • first element of chunk goes to first row.
    • element at rowsNum index goes to last row
    • other rows those are neither first or last rows will adopt elements at rowNumber and (chunkSize - rowNumber). rowNumber is fillRow variable in the code.

    We create a buffer r, and loop from first row to last row to fill the buffer one by one, according to above rules.

    Although this solution has nested loops but in fact the inner loops skip the elements to ensure looking at each element once. Therefore, it is O(N).

    /**
     * @param {string} s
     * @param {number} numRows
     * @return {string}
     */
    var convert = function(s, numRows) {
        
        if (s == "") return "";
        if (numRows == 1) return s;
        
        let r = [];
        let rIndex = 0;    
        let chunkSize = 2 * numRows - 2;
        let i = 0;
       
        let fillRow = 0;
        while (fillRow < numRows) {
            if (fillRow == 0) {
                for(let i = 0; i < s.length; i += chunkSize) { r[rIndex++] = s[i]; }
            } else if (fillRow == numRows - 1) {
                for(let i = fillRow; i < s.length; i += chunkSize) { r[rIndex++] = s[i]; }
            } else {
                for(let i = 0; i< s.length; i += chunkSize) {
                    let idx1 = i + fillRow;
                    let idx2 = i + chunkSize - fillRow;                 
                    if (idx1 < s.length) r[rIndex++] = s[idx1];
                    if (idx2 < s.length) r[rIndex++] = s[idx2];
                }
            }
            fillRow++;
        }   
        
        return r.join("");
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.