Zigzag Conversion
Medium · Strings · String · Simulation
Problem
Write the characters of s in a zigzag over numRows rows: go down the first column one row at a time, then diagonally up to the right until the top row, then down again, and so on. With numRows = 3, "PAYPALISHIRING" is laid out as
Then read the rows from top to bottom, left to right, and return the result: here "PAHNAPLSIIGYIR".
Examples
Input: s = "PAYPALISHIRING", numRows = 3 Output: "PAHNAPLSIIGYIR"
Row 0 is PAHN, row 1 APLSIIG, row 2 YIR.
Input: s = "PAYPALISHIRING", numRows = 4 Output: "PINALSIGYAHRPI"
The rows are PIN, ALSIG, YAHR and PI.
Input: s = "A", numRows = 1 Output: "A"
With one row there is no zigzag.
Constraints
- 1 <= s.length <= 1000
- s holds English letters (both cases), , and .
- 1 <= numRows <= 1000
Approaches
- Fill the 2-D grid — time O(n · numRows), space O(n · numRows)
Follow-up
Can you run it backwards, recovering s from the row-by-row text and numRows? And can you return the rows themselves instead of their concatenation?
Related problems
Start free on Cariara · Coding problems · System design studio
