In this LeetCode challenge we’re asked to convert a string to its ZigZag equivelant, and then output said ZigZag in line order. Sound confusing? Yep, it should do.
First off, what is a ZigZag? Well, in the context of this question, it’s a way of formatting text that first descends along a column, then ascends on a diagonal, and then repeats. For example, a ZigZag of the word “HELLOTHERE”, with 3 rows, would look like this:
H O R
E L T E E
Though, personally, I find it a little easier to visualise with 4+ rows, so let’s try “DUNCANMCARDLE” with 4:
D M E
U N C L
N A A D
But the further complication with this question is that they’re not interested in the ZigZag itself, but rather each row of the constructed ZigZag. So to use the examples above, the output for the “HELLO” ZigZag would be “HORELTEELH”, and the output for “DUNCANMCARDLE” would be “DMEUNCLNAADCR”.
Solution #1: Multi-dimensional array
In this solution, we loop through the input string’s letters, and store each one in a multi-dimensional array that visually represents the eventual ZigZag. We do this by keeping a couple of markers:
headingDown. What these two markers do, is they enable us to keep track of which row should get the next letter, and whether we should head up or down after processing that letter. Once we then head up or down, we check if we’ve exceeded the size of the ZigZag, and then flip to head in the other direction. In other words, we zig-zag through the string!
What we end up with is a multi-dimensional array very similar to the data presented above. For example, here’s the “DUNCANMCARDLE” output:
[ 'D', 'M', 'E' ],
[ 'U', 'N', 'C', 'L' ],
[ 'N', 'A', 'A', 'D' ],
[ 'C', 'R' ]
With this output, we can then simply
.join() each row, and concatenate them all together, to get our intended output.