The problem
Write a string in a zigzag on numRows rows, then read it row by row.
Input: "PAYPALISHIRING", 3 rows Output: "PAHNAPLSIIGYIR"
Picture it
Picture letters walking down and up a staircase of rows: down to the bottom row, back up to the top, and so on. Each row collects the letters that land on it; joining the rows gives the answer.
Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.
The key idea
Simulate the row index bouncing between 0 and numRows − 1. O(n).
Python solution
def convert(s, rows):
if rows == 1:
return s
lines = [""] * rows
r, step = 0, 1
for ch in s:
lines[r] += ch
if r == 0: step = 1
elif r == rows - 1: step = -1
r += step
return "".join(lines)In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.