# Solution by awice

• #### Approach #1: Simulation [Accepted]

Intuition

We translate to code the steps a human would take to create the string.

Algorithm

For each letter in the string, we place that letter in the correct row `cur_row`, then move our pointer to the next correct row. We will need to know not only the location of our pointer, but it's current direction `cur_direction`: `1` for down and `-1` for up.

Care must also be taken in the case that `numRows` is `1`.

Python

``````class Solution(object):
def convert(self, S, numRows):
rows = [[] for _ in range(numRows)]
cur_row = 0
cur_direction = 1

for char in S:
rows[cur_row].append(char)
cur_row += cur_direction
if cur_row == numRows:
cur_row = max(numRows - 2, 0)
cur_direction *= -1
elif cur_row == -1:
cur_row = min(numRows - 1, 1)
cur_direction *= -1

return "".join("".join(row) for row in rows)
``````

Complexity Analysis

• Time Complexity: \$\$O(N)\$\$, where \$\$N\$\$ is the length of the string. We loop through every character in the string and do constant work inside the loop.

• Space Complexity: \$\$O(N)\$\$ to hold the answer, which has size proportional to the initial string.

#### Approach #2: Index Generator [Accepted]

Intuition

Because knowing what row the next letter goes in is tricky, we write a helper generator that returns these indices.

Algorithm

We proceed as before: we will loop through the string and place the characters in rows. The index that we place it will be given by a generator.

The generator is straightforward: if there are `N` rows, we go from `0` to `N-1`, then from `N-2` to `1`, then start over.

Python

``````class Solution(object):
def convert(self, S, numRows):
rows = [[] for _ in range(numRows)]
def staircase_indexes(N):
while True:
for i in range(N):
yield i
for i in range(N-2, 0, -1):
yield i

gen_index = staircase_indexes(numRows)
for c in S:
rows[next(gen_index)].append(c)

return "".join("".join(row) for row in rows)
``````

Complexity Analysis

• \$\$O(n)\$\$ time and space complexity. The analysis is the same as in Approach #1.

#### Approach #3: Mathematical [Accepted]

Intuition

For each row, let's try to know mathematically which string indices are going to be taken.

Algorithm

Say there are `N` rows. When `N > 1`, there are `2N-2` indices in the loop: `0, 1, ..., N-2, N-1, N-2, ..., 1` before the pattern of row indices repeats again. In the first and last row, we have string indices (zero-indexed) \$\$0 \mod 2N-2\$\$ and \$\$N-1 \mod 2N-2\$\$. In other rows \$\$i\$\$, we have string indices \$\$i\$\$ and \$\$2N-2-i\$\$.

Python

``````class Solution(object):
def convert(self, S, N):
if N == 1:
return S

ans = []
for row in range(N):
if row == 0 or row == N-1:
ans.append(S[row::2*N-2])
else:
for i in range(0, len(S), 2*N-2):
for j in (i + row, i + 2*N-2-row):
if j < len(S):
ans.append(S[j])

return "".join(ans)
``````

Complexity Analysis

• \$\$O(n)\$\$ time and space complexity. The analysis is the same as in Approach #1.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.