Strings · 131Medium
Zigzag Conversion
Write the string s in a zigzag pattern across numRows rows, then read it off row by row and return the resulting string.
Constraints
- 1 <= s.length <= 1000
- 1 <= numRows <= 1000
- s consists of English letters, ',' and '.'.
Examples
convert("PAYPALISHIRING", 3) -> "PAHNAPLSIIGYIR"
convert("PAYPALISHIRING", 4) -> "PINALSIGYAHRPI"
convert("AB", 1) -> "AB" // one row is unchanged
convert("ABC", 5) -> "ABC" // numRows >= s.length is unchanged
convert("ABCD", 2) -> "ACBD"
convert("ABCDEFG", 4) -> "AGBFCED"Edge cases
- numRows = 1 returns the input unchanged.
- numRows >= s.length also returns the input unchanged.
- The direction flips at the top AND bottom rows.
Show the target complexity (spoiler)
- Naive
- Physically building a numRows x n character matrix wastes O(n * numRows) space.
- Target
- O(n) time, O(n) space — append each character to a per-row buffer, flipping the row direction at the first and last row, then concatenate the rows.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/15-strings/131-zigzag-conversion.js ./practice c 131