Reference: LeetCode
Difficulty: Medium

## Problem

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"

Example:

## Analysis

### ZigZag Simulation

Use extra numRows buckets to simulate the ZigZag process.

Note:

Time: $O(N)$
Space: $O(N)$

### Visit by Row

By observation, consider the following cases:

• Characters in row 0.
• Characters in row numRows - 1.
• Characters in inner rows.

Just analyze the examples below and find the rules for indexing. The index for inner rows is tricky and a bit complex. Try to think how to make the current row number contribute.

Note: Be careful of the corner case numRows == 1.

Time: $O(N)$
Space: $O(1)$

Comment
Junhao Wang
Hi, I was a master student at USC studying Computer Science.
Newest Comments
loading...
Info
Article :
50
Total Count :
82.3k
UV :
PV :
Last Push :