This content originally appeared on DEV Community and was authored by kevin074
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.
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 N
A P L S I I G
Y 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!
This content originally appeared on DEV Community and was authored by kevin074
kevin074 | Sciencx (2022-02-19T08:55:29+00:00) Leetcode diary: 6. Zigzag Conversion. Retrieved from https://www.scien.cx/2022/02/19/leetcode-diary-6-zigzag-conversion/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.