Your Web News in One Place

Help Webnuz

Referal links:

Sign up for GreenGeeks web hosting
February 19, 2022 08:55 am GMT

Leetcode diary: 6. Zigzag Conversion

This is a new series where I document my struggles of leetcode questions hoping seeing however small of an audience I get gives me the motivation to continue.

link

This question is...interesting... It has a 1:2 ratio for likes:dislikes. However it also has a pretty high frequency of being asked in a real interview, mostly from Amazon. So I decided to give this a go even though the question itself is confusing af.

the question is that given a string, we want to rearrange it in a "zig zag" fashion. What this means is that you read from up to down, then you read upwards until at the top again.
ex: PAYPALISHIRING (paypal is hiring), below is the zigzag

P   A   H   NA P L S I I GY   I   R

Honestly this problem probably took longer to understand how the hell it is arranging rather than taking the time to come up with an algorithm for it.

Take you time to understand how the string is rearranged and read below:
.
.
.
.
.
.
.
I started imagining this question as via a 2D array, it's definitely a lot easier seeing the arrangement above as 2D arrays first.

below is how I came up with a step by step understanding for the algorithm:

what I notice is that     1.) start at 0,     2.) whenever starting at 0, we put in one letter into each row    3.) after that we are at currentRow = numRows-1;    4.) next we are at numRows-2;    5.) we then only put a letter for row == numRows-2, all else is ""    6.) we then decrement currentRow and repeat #5 until currentRow == 0     7.) we repeat 1 to 6 until all letters are used.    we can then loop through the matrix and get the concatenated string    we don't need a 2d array, we can just use array of strings

full code below:

var convert = function(s, numRows) {        let currentRow = 0;     let currentSIndex = 0;    let upwardIndex = numRows-1;    const matrix = new Array(numRows).fill("");    while (currentSIndex < s.length) {        while(currentRow < numRows && currentSIndex < s.length) {            matrix[currentRow++] += s[currentSIndex++]        }        currentRow--                    //cause currentRow === numRows at this point;        if(numRows >= 2) currentRow--;  //All start at numRows-2 except if numRows === 1        while(currentRow > 0) {            upwardIndex = numRows-1;            while(upwardIndex >-1 && currentSIndex < s.length) {                if(upwardIndex === currentRow) {                    matrix[upwardIndex] += s[currentSIndex++];                }                 upwardIndex--            }            currentRow--;        }    }    return matrix.join("")};

The only special case is row == 1. row ==2 required some thinking to see that it is the same as everything else.

Let me know anything on your mind after reading through this, THANKS!


Original Link: https://dev.to/kevin074/leetcode-diary-6-zigzag-conversion-464e

Share this article:    Share on Facebook
View Full Article

Dev To

An online community for sharing and discovering great ideas, having debates, and making friends

More About this Source Visit Dev To