Zigzag Conversion
The key idea
Walking the string once, the row index bounces between
0 and numRows - 1: it goes down until it hits the bottom row, then up until it hits the top, then down again. Track that direction and append each character to its current row's bucket.Problem
The string s is written in a zigzag pattern on a given number of rows numRows, like this (you may want to display this pattern in a fixed font for better legibility):
The characters of s are placed top-to-bottom down the first column, then move diagonally up-and-to-the-right until reaching the top row, and the pattern repeats. After the whole string is laid out, you then read it row by row — left to right, top row first — to produce a new string.
Write the code that takes the original string s and the integer numRows and returns this transformed reading of it. When numRows is 1, the zigzag has no diagonals, so the result is simply s itself.
Constraints
1 <= s.length <= 1000sconsists of English letters (lower-case and upper-case),','and'.'1 <= numRows <= 1000
Examples
Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Input: s = "A", numRows = 1
Output: "A"
Complexity
Time: O(n) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization