In this post, we are going to look at my solution to the “Zigzag Conversion” from LeetCode using TypeScript.
The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
And then read line by line: “PAHNAPLSIIGYIR”
Write the code that will take a string and make this conversion given a number of rows:
We can forget about all the zigzag stuff and think of the problem as rows of string instead. We simply have to loop through each character and concatenate it to the appropriate string.
For example, the conversion of
"PAYPALISHIRING" with 3 rows is
The pattern above is the same as (considering that we’re going to join them line by line in the end)
And finally, we can concatenate the strings and get
The time complexity of this approach is
n equals the length of the input string.
Translating our approach to code:
Let me explain the code:
- We create an array of empty string the size of the number of rows.
- We then create a cursor and a boolean flag to control whether the cursor should be increasing or decreasing.
- We loop through each character in the string.
- We concatenate the char with the string that the current cursor is pointing at.
- We adjust the flag if needed.
- We modify the cursor based on the flag.
- Note that the cursor shouldn’t be a negative number, so we have an additional check before decreasing the cursor.
- We return all the string inside the array joined together.
That’s it for LeetCode’s “Zigzag Conversion” 🎉. The result is also very satisfying.
You can also find the code on my Github.